題目描述?Description

1920年的芝加哥，出現了一群強盜。如果兩個強盜遇上了，那么他們要么是朋友，要么是敵人。而且有一點是肯定的，就是：

我朋友的朋友是我的朋友；

我敵人的敵人也是我的朋友。?

兩個強盜是同一團伙的條件是當且僅當他們是朋友。現在給你一些關于強盜們的信息，問你最多有多少個強盜團伙。

輸入描述?Input Description

輸入文件gangs.in的第一行是一個整數N(2<=N<=1000)，表示強盜的個數（從1編號到N）。?第二行M(1<=M<=5000)，表示關于強盜的信息條數。?以下M行，每行可能是F?p?q或是E?p?q（1<=p?q<=N），F表示p和q是朋友，E表示p和q是敵人。輸入數據保證不會產生信息的矛盾。

輸出描述?Output Description

輸出文件gangs.out只有一行，表示最大可能的團伙數。

樣例輸入?Sample Input

6
4
E?1?4
F?3?5
F?4?6
E?1?2

樣例輸出?Sample Output

3

數據范圍及提示?Data Size & Hint

2<=N<=1000

1<=M<=5000

1<=p?q<=N

解析： 說實話這道題在想怎么處理敵人的敵人是朋友時我糾結了好久，但是在看了一位大牛的思路后我想通了。這道題不能想太死板，做以下幾個步驟就行 1.輸入時新開一個數組記錄當前的敵人，如果已經記錄那就可以讓敵人的敵人變成朋友：比如樣例中E 1 4 ，我發現這時候的e數組的1,4下標 為空，我就讓e[1]=4,e[4]=1;到了E 1 2時，發現e[1]有值了，那么2和4就是朋友關系change(2,4);e[2]=1;e[1]=2; 2.做到這里時，你可能會覺得2會把4給覆蓋了，但其實沒有問題，e[1]這時候的值是2,而2和4已經處于一個集合里面了，就不會影響后來的分團伙 可能說的不是很清楚，咱還是看代碼吧 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #define maxn 5005 using namespace std;int f[maxn],e[maxn],vis[maxn]; int n,m,q;void first() {for(int i=1;i<=n;i++){f[i]=i;e[i]=0;} }int find_father(int x) {if(f[x]==x)return x;return find_father(f[x]); }void change(int a,int b) {int af=find_father(a),bf=find_father(b);if(af!=bf){f[max(bf,af)]=min(bf,af);//讓所有的點的根都盡量偏小，是方便統一 } }int main() {scanf("%d%d",&n,&m);first();for(int i=1;i<=m;i++){int a,b;char c;cin>>c>>a>>b;if(c=='F')change(a,b);else{if(e[a]!=0)change(e[a],b);//敵人的敵人就是朋友 if(e[b]!=0)change(e[b],a);e[a]=b;e[b]=a;//標記敵人 } }for(int i=1;i<=n;i++){f[i]=find_father(i);//讓所有人都找到自己的集合 }int ans=0;for(int i=1;i<=n;i++){if(vis[find_father(i)]==0){ans++;vis[find_father(i)]=1;}}printf("%d",ans);}

　　

轉載于:https://www.cnblogs.com/Danzel-Aria233/p/7163289.html

總結

以上是生活随笔為你收集整理的[codevs2597]团伙并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。