hdu 6109 数据分割(并查集+set)

题目链接:hdu 6109 数据分割

题意:

给你一些不等和相等关系,然后分割,每次都按第一个不成立的等式分割。

题解:

由于相等关系具有传递性,不等关系不具有传递性。

所以相等关系可以由并查集来存储,不相等关系用set来存,目的是为了让查找log(n)

然后在两个集合进行合并的时候,要采用启发式合并的方式,及每次都将小的集合的每个元素放进大的集合。

这样启发式合并的总复杂度为nlog(n)。然后加上set的insert复杂度,总负责度就是n*log(n)2

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 
 5 const int N=1e5+7;
 6 set<int>st[N];
 7 int n,ans[N],ed,cnt,a,b,c,f[N],S[N],top;
 8 
 9 int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
10 void get(){
11     ans[++ed]=cnt,cnt=0;
12     while(top)
13     {
14         f[S[top]]=S[top];
15         st[S[top]].clear();
16         top--;
17     }
18 }
19 void merge(int x,int y)
20 {
21     if(st[x].size()<st[y].size())swap(x,y);
22     for(int it:st[y])st[x].insert(find(it));
23     f[y]=x;
24 }
25 
26 int main(){
27     while(~scanf("%d",&n))
28     {
29         F(i,1,n)f[i]=i,st[i].clear();
30         ed=0,cnt=0,top=0;
31         F(i,1,n)
32         {
33             scanf("%d%d%d",&a,&b,&c);
34             cnt++,S[++top]=a,S[++top]=b;
35             if(a==b&&c==1)continue;
36             if(a==b&&c==0){get();continue;}
37             if(c==1)
38             {
39                 int fx=find(a),fy=find(b);
40                 if(st[fx].find(fy)!=st[fx].end())get();
41                 else merge(fx,fy);
42             }else
43             {
44                 int fx=find(a),fy=find(b);
45                 if(fx==fy)get();
46                 else st[fx].insert(fy),st[fy].insert(fx);
47             }
48         }
49         printf("%d
",ed);
50         F(i,1,ed)printf("%d
",ans[i]);
51     }
52     return 0;
53 }
View Code
原文地址:https://www.cnblogs.com/bin-gege/p/7358026.html