数据分割
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1119 Accepted Submission(s): 268Problem Description小w来到百度之星的赛场上，准备开始实现一个程序自动分析系统。这个程序接受一些形如xi=xj 或 xi≠xj 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。
输入包含多组数据。
然而粗心的小w不幸地把每组数据之间的分隔符删掉了。
他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。请帮助他恢复这些分隔符。
Input第1行：一个数字L，表示后面输入的总行数。之后L行，每行包含三个整数，i,j,e，描述一个相等/不等的约束条件，若e=1，则该约束条件为xi=xj ，若e=0，则该约束条件为 xi≠xj 。
i,j,L≤100000
xi,xj≤L
Output输出共T+1行。第一行一个整数T，表示数据组数。
接下来T行的第i行，一个整数，表示第i组数据中的约束条件个数。
Sample Input6
2 2 1
2 2 1
1 1 1
3 1 1
1 3 1
1 3 0Sample Output1
6SourceRecommend
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6109
题目大意：
给一些等式或不等式，xi=xj或xi!=xj，求一个划分，使得每一部分内的等式组去掉最后一个式子后成立。
题目思路：
【并查集+set】
开一个set Qi记录当前与这个元素Xi所在集合Si不相等的编号。
若条件为相等，判断其中一个元素Xi所在集合Si是否在另一元素Xj不相等集合Qj的set中，不在则将两个元素并成一个集合，并将不等的元素集合也合并（小的并到大的），否则不合法
若条件为不等，则判断这两个元素是否属于同一集合，是的话不合法，否则将对方加入到自己的set 中。
/****************************************************
Author : Coolxxx
Copyright 2017 by Coolxxx. All rights reserved.
BLOG : http://blog.****.net/u010568270
****************************************************/
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define mem(a,b) memset(a,b,sizeof(a))
const double EPS=0.00001;
const int J=;
const int MOD=;
const int MAX=0x7f7f7f7f;
const double PI=3.14159265358979323;
const int N=;
const int M=;
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
int fa[N],sz[N];
set<int>a[N];
int zhao(int aa)
{
if(fa[aa]==aa || fa[aa]==)return aa;
return fa[aa]=zhao(fa[aa]);
}
bool Find(set<int>q,int x)
{
set<int>::iterator it;
for(it=q.begin();it!=q.end();it++)
{
if(zhao(*it)==x)return ;
}
return ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z,fx,fy;
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
while(~scanf("%d",&n))
{
lll=;sz[]=;k=;
for(i=;i<=n;i++)fa[i]=i;
for(i=;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
k=max(k,x);
k=max(k,y);
fx=zhao(x);
fy=zhao(y);
if(a[fy].size()>a[fx].size()swap(fx,fy);
if(z)
{
if(Find(a[fy],fx))
{
sz[++lll]=i;
for(j=;j<=k;j++)fa[j]=j;
for(j=;j<=k;j++)a[j].clear();
k=;
}
else
{
fa[fy]=fx;
a[fx].insert(a[fy].begin(),a[fy].end());
}
}
else
{
if(fx==fy)
{
sz[++lll]=i;
for(j=;j<=k;j++)fa[j]=j;
for(j=;j<=k;j++)a[j].clear();
k=;
}
else
{
a[fx].insert(fy);
a[fy].insert(fx);
}
}
}
for(j=;j<=k;j++)a[j].clear();
printf("%d\n",lll);
for(i=;i<=lll;i++)
printf("%d\n",sz[i]-sz[i-]);
}
return ;
}
/*
//
//
*/