poj 1611 The Suspects 并查集变形题目
Time Limit: 1000MS | Memory Limit: 20000K | |
Total Submissions: 20596 | Accepted: 9998 |
Description
Input
Output
Sample Input
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0
Sample Output
4 1 1
讲解:使用并查集,每输入一行学生编号数据后,都判断第一个学生编号的祖先是否和后面每一个学生编号的祖先相同,若不同,则将第一个编号的祖先变为该后面编号的祖先,
将集合合并,且每合并一次,第一个编号的祖先上的元素个数都等于合并之前两个祖先上的元素个数之和(最初,每一个编号的祖先都是该编号自身,且对应的元素个数都为一),
最后输出编号为0的祖先上的元素个数即可
总结及出错情况:该题主要就是使用并查集,注意在合并的时候祖先上的元素个数要更新,且最初的时候每一个编号的祖先上的元素个数都是1,最易出错的就是在输入的数据中没有0
就以为没有感染嫌疑者,其实这种情况应该是有一个,因为0在的号代表的学生就是感染嫌疑者
AC代码:
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 #define N 30010 7 int vis[N],parent[N],m,n; 8 void begin() 9 { 10 for(int i=0;i<m;i++) 11 { 12 parent[i]=i; 13 vis[i]=1; 14 } 15 } 16 int find (int x) 17 { 18 if(parent[x]!=x) 19 { 20 parent[x]=find(parent[x]); 21 } 22 return parent[x]; 23 } 24 int query(int x,int y) 25 { 26 int px=find(x); 27 int py=find(y); 28 if(px!=py) 29 { 30 parent[py]=px; 31 vis[px]=vis[py]+vis[px];//父亲不同的话统计个数,相同的话,不用统计了; 32 } 33 } 34 int main() 35 { 36 int first,k,a; 37 while(cin>>m>>n && m+n) 38 { 39 begin(); 40 for(int i=0; i<n; i++) 41 { 42 scanf("%d %d", &k,&first); // 首先把第一个输入的,当成父亲; 43 for(int j=1; j<k; j++) 44 { 45 scanf("%d",&a); //后面的如果有父亲,并且不和第一个父亲相同, 46 query(first ,a); //则后面的父亲,为第一个的父亲 47 } 48 } 49 printf("%d\n",vis[find(0)]); 50 } 51 return 0; 52 }
优质内容筛选与推荐>>