終於找到這題的提交鏈接了，劉汝佳那本書81頁有這題的的題解，不重復了。 我覺得這題思維還是很饒人的。 題目大體的說： 1.我朋友的朋友是我的朋友； 2.我敵人的敵人是我的朋友； 所有是朋友的人組成一個團伙。告訴你關於這N個人的M條信息，即某兩個人是朋友，或者某兩個人是敵人，請你編寫一個程序，計算出這個城市最多可能有多少個團伙？ 用並查集來記錄，其中e[i]記錄i的是i的敵人組成的團伙。 [cpp] #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <algorithm> #include <stack> #include <queue> #include <map> using namespace std; int f[1005]; int e[1005]; int vis[1005]; int findset(int a) { if(a == f[a]) { return a; } f[a] = findset(f[a]); return f[a]; } void unionset(int a,int b) { a = findset(a); b = findset(b); if(a!=b) { f[b] = a; } } int main() { /*#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif*/ int n,m; char c; int a,b; while(scanf(" %d %d",&n,&m)!=EOF) { memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); for(int i=1; i<=n; i++) { f[i] = i; } for(int i=0; i<m; i++) { scanf(" %c %d %d",&c,&a,&b); //printf("c = %c\n",c); if(c == 'F') { unionset(a,b); } else if(c == 'E') { if(e[a] == 0) { e[a] = b; } else { unionset(e[a],b); } if(e[b] == 0) { e[b] = a; } else { unionset(e[b],a); } } } int sum = 0; for(int i=1; i<=n; i++) { www.2cto.com int cur = findset(i); if(vis[cur] == 0) { vis[cur] = 1; sum++; } } printf("%d\n",sum); } return 0; }
