首页 > 代码库 > 【并查集】BZOJ1370- [Baltic2003]Gang团伙
【并查集】BZOJ1370- [Baltic2003]Gang团伙
【题目大意】
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、 我朋友的朋友是我的朋友； 2、 我敌人的敌人是我的朋友； 所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
【思路】
水………NOIP的小孩都不屑于玩……
把i拆成i和i+n,其中i表示i的朋友，i+n表示i的敌人。对于(i,j):
(1)i，j是朋友，那么合并i和j。
(2)i，j不是朋友，那么合并i和j+n,j和i+n，代表敌人的敌人是我的朋友。
*注意，如果i和j是敌人，那么它们的敌人不一定是朋友。所有不要合并i+n和j+n。
好水啊……
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=5000; 7 int u[MAXN],h[MAXN],appear[MAXN]; 8 int n,m,gang; 9 10 int find(int x)11 {12 int r=x,temp;13 while (u[r]!=r) r=u[r];14 while (x!=r)15 {16 temp=u[x];17 u[x]=r;18 x=temp;19 }20 return r;21 }22 23 void union_set(int fa,int fb)24 {25 if (h[fa]>=h[fb])26 {27 u[fb]=fa;28 if (h[fa]==h[fb]) h[fa]++;29 }30 else u[fa]=fb;31 }32 33 void init()34 {35 for (int i=1;i<=2*n;i++)36 {37 u[i]=i;38 h[i]=1;39 }40 }41 42 void solve()43 {44 scanf("%d%d",&n,&m);45 init();46 for (int i=1;i<=m;i++)47 {48 char op[2];49 int u,v;50 scanf("%s%d%d",op,&u,&v);51 if (op[0]==‘F‘)52 {53 int fa=find(u),fb=find(v);54 if (fa!=fb) union_set(fa,fb);55 }56 else57 {58 int fa=find(u),fb=find(v+n);59 if (fa!=fb) union_set(fa,fb);60 fa=find(v),fb=find(u+n);61 if (fa!=fb) union_set(fa,fb);62 }63 }64 }65 66 void getans()67 {68 for (int i=1;i<=n;i++) u[i]=find(i);69 memset(appear,-1,sizeof(appear));70 gang=0;71 for (int i=1;i<=n;i++)72 {73 if (appear[u[i]]==-1)74 {75 gang++;76 appear[u[i]]=1; 77 }78 }79 printf("%d",gang);80 }81 82 int main()83 {84 solve();85 getans();86 return 0;87 }
【并查集】BZOJ1370- [Baltic2003]Gang团伙
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。