hdu 6109 数据分割

/**
 * 题目描述有点坑，勉强能读懂，大致意思，有多组约束条件。原本每组数据之间是有分界符号的
 * 现在分界符号没了，让你找出原来每组数据多少个条件，并且告诉，每组的最后一个条件会使得与前面的
 * 条件冲突。
 * 
 * 解题思路：膜拜大佬的解法，并查集+set大法。a==b 的约束条件用并查集，a!=b的约束给这个集合建边。
 * 代表这两个集合不等。本题时间复杂度不太会计算。这样总感觉极限数据会TLE。结果就AC了。很绝望！
 * 提供一种解题思路吧，倍增感觉很厉害，目前不知道怎么写》》
 */
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long LL;
const int INF=2e9+1e8;

const int MOD=1e9+7;
const double eps=0.0000000001;
void fre()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
#define MSET(a,b) memset(a,b,sizeof(a))

const int maxn=1e5+10;
int a[maxn],b[maxn],e[maxn],pre[maxn];
set<int>G[maxn];
void init(int n) //清空并查集和set图
{
    for(int i=1;i<=n;i++) 
        pre[i]=i,G[i].clear();
}
int F(int x)
{
    return x==pre[x]?x:pre[x]=F(pre[x]);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        vector<int>ans;
        init(n);
        int sz=0;
        for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&e[i]);
        for(int i=1;i<=n;i++)
        {
            sz++;
            int x=F(a[i]),y=F(b[i]);
            if(e[i]) //如果是 a==b
            {
                if(x==y) continue;//a，b在同一个集合，a==b成立，不管。
                else 
                {
                    if(G[x].find(y)!=G[x].end()) //a==b；  a，b不在一个集合，存在边说明两个集合不等，显然不成立；统计答案
                    {
                        ans.push_back(sz);
                        sz=0;
                        init(n);
                    }
                    else // a==b； a，b不在一个集合，a，b所在的集合不存在边，成立；
                    {
                        set<int>::iterator it;
                        for(it=G[x].begin();it!=G[x].end();it++) //合并set，
                        //意思是：将与x相连的边删掉，让他们和y相连
                        {
                            G[y].insert(*it);
                            G[*it].erase(x);
                            G[*it].insert(y);
                        }
                        G[x].clear();
                        pre[x]=y;
                    }
                }
            }
            else // 判断 a!=b
            {
                if(x==y) // a！=b ，a，b同在一个集合，不成立；
                {
                    ans.push_back(sz);
                    sz=0;
                    init(n);
                }
                else G[x].insert(y),G[y].insert(x);//a！=b，a，b不在同一个集，两集合之间建边；
            }
        }
        printf("%d
",(int)ans.size());
        for(int i=0;i<(int)ans.size();i++)
        printf("%d
",ans[i]);
    }
    return 0;
}

/**************************************************/
/**             Copyright Notice                 **/
/**  writer: wurong                              **/
/**  school: nyist                               **/
/**  blog  : http://www.cnblogs.com/coded-ream/  **/
/**************************************************/