RT

?

題目描述

?

1920年的芝加哥，出現(xiàn)了一群強(qiáng)盜。如果兩個(gè)強(qiáng)盜遇上了，那么他們要么是朋友，要么是敵人。而且有一點(diǎn)是肯定的，就是：

?

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

?

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

?

兩個(gè)強(qiáng)盜是同一團(tuán)伙的條件是當(dāng)且僅當(dāng)他們是朋友?，F(xiàn)在給你一些關(guān)于強(qiáng)盜們的信息，問你最多有多少個(gè)強(qiáng)盜團(tuán)伙。

?

輸入輸出格式

輸入格式：

?輸入的第一行是一個(gè)整數(shù)N(2<=N<=1000)，表示強(qiáng)盜的個(gè)數(shù)（從1編號到N）。 第二行M(1<=M<=5000)，表示關(guān)于強(qiáng)盜的信息條數(shù)。 以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敵人。輸入數(shù)據(jù)保證不會產(chǎn)生信息的矛盾。

?輸出格式：

?輸出只有一行，表示最大可能的團(tuán)伙數(shù)。

?

輸入：? 　　　　?輸出：

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

?

一看這題，是一道并查集的好?水??題，但好像和以往的不太一樣；

想一想，好像是個(gè)數(shù)學(xué)集合；

把朋友并一起，把敵人的敵人并到朋友；

par[n]存 朋友，par[n*2]存敵人；

然后就好了；

#include <cstdio> #include <algorithm>using namespace std;struct b {int par[100010];inline void ih(int n){for(int i=1;i<=2*n;i++)par[i]=i;}int f(int x){return par[x]=(par[x]==x)?x:f(par[x]);}int u(int x,int y){par[f(y)]=f(x);} }s; int n,m,sum; int x,y; char c; int main() {scanf("%d",&n);scanf("%d",&m);s.ih(n);for(int i=1;i<=m;++i){scanf("%s%d%d",&c,&x,&y);if(c=='F'){s.u(x,y);}else if(c=='E'){s.u(y,x+n); //不要并反了s.u(x,y+n);}}for(int i=1;i<=n;++i){if(s.par[i]==i) sum++; }printf("%d",sum); } 騷代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/AidenPearce/p/8289730.html

總結(jié)

以上是生活随笔為你收集整理的并查集的一般操作 ③的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。