題目描述
Mrs.Chen是一個很認真很稱職的語文老師 … 所以,當她看到學生作文里的人物關系描述得非常的麻煩的時候,她非常生氣,于是宣布:凡是作文里有冗余關系的,一率罰抄出師表10次…同學們非常的恐懼,于是,每當他們寫出一篇作文,都要拿來你這個語文兼OI天才這里,問你有沒有冗余的關系 … 時間一久,你也煩了,于是就想寫個程序來代勞 … 現在這里有一篇作文,有n句描述人物關系的句子,描述了n個人的關系 每條句子的定義是這樣的 X Y 它的意思是:X認識Y Y也認識X 現在要你求出文中冗余關系的數目. 注意: 假如A認識B,B認識C,則A也認識C 冗余關系的定義是指 : 即使沒有這條關系,原圖的所有關系照樣成立.

輸入
第一行,兩個整數,表示句子數量(n)，表示人數(m)。 接下來n行,每行兩個數,意義在描述里已經說了.

輸出
一個整數,表示冗余關系的數目.

樣例輸入
3 3
1 2
1 3
2 3
樣例輸出
1
提示

1< =n,m< =1000

#include <cstdio> int father[40010],ans,n,m; int get_fa(int x){if(x!=father[x])return(get_fa(father[x])); } void join(int x,int y){int t[2];t[0]=get_fa(x);t[1]=get_fa(y);if(t[0]!=t[1]) father[t[0]]=t[1]; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) father[i]=i;while(m--){int x,y;scanf("%d%d",&x,&y);join(x,y);}for(int i=1;i<=n;i++)if(father[i]==i) ans++;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的「TYVJ1017」冗余关系的全部內容，希望文章能夠幫你解決所遇到的問題。

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