The Suspects
題目：編號為0的人有傳染病，同組中只要有一個人有傳染病，該組的人都被看做有傳染病，一個人可以在多組中，問有多少人有傳染病，
思路：并查集，需要壓縮并查集的樹，編號小的點優先作為祖先（0為root），并查集程序中傳遞祖先的同時傳遞祖先是否是病人，最后再次遍歷所有人，使得祖先是病人子孫不是病人的情況解決，因為我們壓縮了并查集的樹，所以這個程序的復雜度不高，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 #include <vector> 6 #include <cmath> 7 8 using namespace std; 9 10 #define ll long long 11 #define pb push_back 12 #define fi first 13 #define se second 14 15 const int N = 3e4 + 10; 16 bool vis[N]; 17 int n, m; 18 19 struct node{ 20 int root, vis; 21 }fa[N]; 22 23 pair<int ,int > Find(int now){ 24 if(fa[now].root == now){ 25 //傳遞祖先和病人資訊 26 return make_pair(fa[now].root, fa[now].vis); 27 }else{ 28 pair<int ,int > tmp = Find(fa[now].root); 29 fa[now].root = tmp.fi; 30 fa[now].vis = tmp.se; 31 return tmp; 32 } 33 } 34 35 void Union(int x, int y) 36 { 37 int fax = Find(x).fi; 38 int fay = Find(y).fi; 39 //編號小的人作為祖先 40 if(fax > fay) swap(fax, fay); 41 fa[fay].root = fax; 42 } 43 44 45 void solve() 46 { 47 while(~scanf("%d%d", &n, &m) && n + m){ 48 for(int x = 0; x < n; ++x){ 49 fa[x].root = x; 50 fa[x].vis = 0; 51 } 52 fa[0].vis = 1; 53 int num, idx, idy; 54 for(int x = 0; x < m; ++x){ 55 scanf("%d%d", &num, &idx); 56 57 for(int y = 1; y < num; ++y){ 58 scanf("%d", &idy); 59 Union(idx, idy); 60 } 61 } 62 63 //再次傳遞病人資訊 64 for(int i = 0; i < n; ++i){ 65 Find(i); 66 } 67 68 int suspects = 0; 69 for(int x = 0; x < n; ++x){ 70 if(fa[x].vis) ++suspects; 71 } 72 73 //printf("suspects = %d\n", suspects); 74 printf("%d\n", suspects); 75 } 76 } 77 78 int main() 79 { 80 81 solve(); 82 83 return 0; 84 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31077.html
標籤：其他
上一篇：4.排序（上）
下一篇：協議生成器工具