題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1789

題意：查找與0有關的人 即為SARS 并查集

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int father[30005]; int rank[30005] ; int n,m; void init() {for(int i = 0 ; i < n ;i ++ ){father[i] = i;rank[i] = 1; //自身節點為1} } int find(int x) {if(x != father[x]) return find(father[x]); return father[x] ; } void Union(int x,int y) {int xx = find(x);int yy = find(y);if(xx == yy) return ;father[xx] = yy;rank[yy] += rank[xx] ; //記錄共同祖先的有多少個成員 } int main() {int a,b,k;while(scanf("%d%d",&n,&m),n+m){init();for(int i = 0; i < m ; i++){scanf("%d%d",&k,&a);for(int j = 1 ; j < k ;j ++){scanf("%d",&b);Union(a,b);a = b ;}}printf("%d\n",rank[find(0)]);//查找0的祖先} }

總結

以上是生活随笔為你收集整理的zoj-1789的全部內容，希望文章能夠幫你解決所遇到的問題。

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