poj1611 并查集基础题
Description
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
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
并查集较为简单，注意路径压缩！~~
#include<iostream>
using namespace std;
int n,m;
int i,j;
int t;
int a,b;
int zero;//remember the set where zero is
int f[30001];//set mark
int c[30001];//set count
int Find(int x)
{
if(f[x]==x)return x;
else
f[x]=Find(f[x]);
return f[x];
}
void Union(int x1,int y1)
{
int x=Find(x1);
int y=Find(y1);
if(x!=y)
{
if(c[x]>=c[y])
{
f[y]=x;
c[x]=c[x]+c[y];
if(y==zero)
zero=x;
}
else
{
f[x]=y;
c[y]=c[x]+c[y];
if(x==zero)
zero=y;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n||m))
{
zero=0;
for(i=0;i<n;i++)
{
f[i]=i;
c[i]=1;
}
for(i=0;i<m;i++)
{
scanf("%d",&t);
scanf("%d",&a);
for(j=0;j<t-1;j++)
{
scanf("%d",&b);
Union(a,b);
}
}
printf("%d\n",c[zero]);
}
return 0;
}
2021年3月01日 21:30
Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards, 123movies app
2022年8月27日 22:29
Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. JDC Result chittagong The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.
2023年11月01日 19:11
definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work
2023年11月14日 13:48
"This is really wonderful, one-of-a-kind as well as really helpful post, i like it. many thanksHello, I wish for to subscribe for this webpage to take latest updates, so where can i do it please assist Greetings, by utilizing Google I discovered your site even as chasing down a similar subject, your site came up, it looks truly intriguing. I bookmarked it.
"
2023年11月14日 14:27
Very nice blog and articles. I am realy very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post.Very nice blog and articles. I am realy very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post.
2023年11月14日 14:56
Good Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information. This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free.
2023年11月14日 15:26
In this article you will read about the best games which can be played on high quality gaming laptops. Give your time to this post and increase your knowledge related to the best games and quality gaming laptops You own a incredibly exciting weblog covering lots of topics I am interested as well.Just bookmarked your internet site so I can read more in the next days Just continue your marvellous artice writing.
2023年11月14日 15:36
stunning, great, I was wondering how to cure skin break out ordinarily. likewise, found your site by google, took in an extraordinary arrangement, now i'm fairly clear. I've bookmark your site and moreover incorporate rss. keep us invigorated.Terrific review, among the list of much better articles Truly go through these days on the net, I recommend to all or any.
2023年11月14日 15:48
I truly welcome this superb post that you have accommodated us. I guarantee this would be valuable for the vast majority of the general population. I am reading your writing well. I know a site that might be helpful for your writing. please read my article and tell us your impressions. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article . This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post . Really i appreciate the effort you made to share the knowledge. The topic here i found was really effective to the topic which i was researching for a long time
2023年11月14日 15:53
stunning, great, I was wondering how to cure skin break out ordinarily. likewise, found your site by google, took in an extraordinary arrangement, now i'm fairly clear. I've bookmark your site and moreover incorporate rss. keep us invigorated.Terrific review, among the list of much better articles Truly go through these days on the net, I recommend to all or any.
2023年11月14日 15:54
"I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work… These fortunate web sites are properly ranked by Bing, and by backlinking your site may also position well.
"
2023年11月14日 16:08
Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work
2023年11月14日 16:15
Good Hello! My Name is Hunan I am a professional SEO expert having 4 years . I am specialized in backlinks, creation, off page SEO, website ranking, website taffic, you will come to the right place, Feel free to contact me I see some amazingly important and kept up to length of your strength searching for in your on the site
2023年11月14日 16:44
WorldClassJackets is serving several customers currently. Our customer products range from Hikers, climbers, skiers, snowboarders, bikers to mountaineers’ jackets, and many other categories both in males and females. worldclassjackets cooperate with the premium courier services working internationally across the globe to bring you the best and efficient shipping and delivery solutions.
2023年11月14日 16:50
It is perfect time to make some plans for the future and it is time to be happy. I've read this post and if I could I desire to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I want to read more things about it!
2023年11月14日 16:57
The article is straightforward, itemized and fastidious! I had a ton of gather in the wake of watching this article from you! I thought that it was intriguing, your article gave me another point of view! I have perused numerous different articles on a similar point, however your article persuaded me
2023年11月14日 17:11
The article is straightforward, itemized and fastidious! I had a ton of gather in the wake of watching this article from you! I thought that it was intriguing, your article gave me another point of view! I have perused numerous different articles on a similar point, however your article persuaded me
2023年11月14日 17:18
I no uncertainty esteeming each and every bit of it. It is an amazing site and superior to anything normal give. I need to grateful. Marvelous work! Every one of you complete an unfathomable blog, and have some extraordinary substance. Keep doing stunning. As a Newbie, I am always exploring online for articles that can be of assistance to me. Thank you
2023年11月14日 17:29
Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post.
2023年11月14日 17:29
Our doctors has a personable and intimate rapport with her patients throughout their inner and outer health journey. She has enjoyed counseling patients and has addressed patients beyond the scope of traditional gynecology. In addition, Our doctors for men in addressing their hormonal imbalances.
2023年11月14日 18:12
Good Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information. This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free.
2023年11月14日 18:18
Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post.
2023年11月14日 18:24
I really wanted to make a quick remark to say thanks to you for the splendid steps you are placing on this site. My extended internet investigation has at the end of the day been paid with useful insight to share with my classmates and friends Just saying thanks will not just be sufficient, for the fantasti c lucidity in your writing. I will instantly grab your rss feed to stay informed of any updates.
2023年11月14日 18:27
It is perfect time to make some plans for the future and it is time to be happy. I've read this post and if I could I desire to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I want to read more things about it!
2023年11月14日 18:35
"This is really wonderful, one-of-a-kind as well as really helpful post, i like it. many thanksHello, I wish for to subscribe for this webpage to take latest updates, so where can i do it please assist Greetings, by utilizing Google I discovered your site even as chasing down a similar subject, your site came up, it looks truly intriguing. I bookmarked it.
"
2023年11月14日 18:53
Good Thank you for another great article. Where else could anyone get that kind of information in such a perfect way of writing? I have a presentation next week, and I am on the look for such information. This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free.
2023年11月14日 19:02
stunning, great, I was wondering how to cure skin break out ordinarily. likewise, found your site by google, took in an extraordinary arrangement, now i'm fairly clear. I've bookmark your site and moreover incorporate rss. keep us invigorated.Terrific review, among the list of much better articles Truly go through these days on the net, I recommend to all or any.
2023年11月14日 19:21
I’m excited to uncover this page. I need to to thank you for ones time for this particularly fantastic read!! I definitely really liked every part of it and i also have you saved to fav to look at new information in your site. I’ve read some good stuff here. Definitely worth bookmarking for revisiting. I surprise how much effort you put to create such a great informative website. Thumbs up guys your doing a really good job.
2023年11月14日 19:26
stunning, great, I was wondering how to cure skin break out ordinarily. likewise, found your site by google, took in an extraordinary arrangement, now i'm fairly clear. I've bookmark your site and moreover incorporate rss. keep us invigorated.Terrific review, among the list of much better articles Truly go through these days on the net, I recommend to all or any.
2023年11月14日 19:35
Good Hello! My Name is Hunan I am a professional SEO expert having 4 years . I am specialized in backlinks, creation, off page SEO, website ranking, website taffic, you will come to the right place, Feel free to contact me I see some amazingly important and kept up to length of your strength searching for in your on the site
2023年11月14日 19:43
Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work
2023年11月14日 19:52
Very nice blog and articles. I am realy very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post.Very nice blog and articles. I am realy very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post.
2023年11月14日 20:09
Well I truly liked reading it. This article provided by you is very effective for good planning..The Kansas City Metro has a lot to present when it comes to blog job possibilities.Truly quite intriguing post. I was searching for this sort of data and delighted in perusing this one. Continue posting. Much obliged for sharing
2023年11月14日 20:36
"I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! keep up the good work… These fortunate web sites are properly ranked by Bing, and by backlinking your site may also position well.
"
2023年11月14日 20:42
Well I truly liked reading it. This article provided by you is very effective for good planning..The Kansas City Metro has a lot to present when it comes to blog job possibilities.Truly quite intriguing post. I was searching for this sort of data and delighted in perusing this one. Continue posting. Much obliged for sharing
2023年11月14日 20:51
Well I truly liked reading it. This article provided by you is very effective for good planning..The Kansas City Metro has a lot to present when it comes to blog job possibilities.Truly quite intriguing post. I was searching for this sort of data and delighted in perusing this one. Continue posting. Much obliged for sharing
2023年11月14日 21:00
Remarkable article, it is particularly useful! I quietly began in this, and I'm becoming more acquainted with it better! Delights, keep doing more and extra impressive! You made such an interesting piece to read, giving every subject enlightenment for us to gain knowledge. Thanks for sharing the such information with us to read this...
2023年11月14日 21:03
I was intrigued accepting that you at whatever point imagined of changing the plan of your site? Its very much made I genuinely like what you've got to say. However, no doubt you might somewhat more in the technique for material at some point so individuals could get along with it better.
2024年1月15日 15:46
you have done a great job. I will definitely dig it and personally recommend to my friends. I am confident they will be benefited from this.
2024年1月15日 17:58
I'm happy to see the considerable subtle element here!.
2024年1月15日 18:44
Thank you for the auspicious writeup. It in fact was an amusement account it. Look advanced to far added agreeable from you! By the way, how could we communicate
2024年1月15日 19:01
"Thanks for such a great post and the review, I am totally impressed! Keep stuff like this coming
"
2024年1月15日 19:47
You have done an amazing job with you website
2024年1月15日 19:49
After research a couple of of the weblog posts in your website now, and I really like your method of blogging. I bookmarked it to my bookmark website record and will probably be checking back soon. Pls check out my site as effectively and let me know what you think. Computers & Accessories
2024年1月15日 20:21
"Thank you for sharing your info. I really appreciate
your efforts and I will be waiting for your further
post thanks once again."
2024年1月15日 20:30
Hello First time I visite your website. I read some posts I got some good information from your posts. I got quality of work from your website. Now I'm your permanent user many Thanks for your writing
2024年1月15日 21:13
That is very helpful for increasing my knowledge in this field.
2024年1月16日 13:47
Hey, I am so thrilled I found your blog, I am here now and could just like to say thank for a tremendous post and all round interesting website. Please do keep up the great work. I cannot be without visiting your blog again and again
2024年1月16日 14:15
Very well written story. It will be useful to everyone who utilizes it, as well as myself. Keep up the good work – i will definitely read more posts
2024年1月16日 17:20
"Very nice post. I just stumbled upon your weblog and wanted to say that I have truly enjoyed browsing
your blog posts. After all I will be subscribing to your feed and I hope you write again soon!"
2024年1月18日 14:06
It’s very informative and you are obviously very knowledgeable in this area. You have opened my eyes to varying views on this topic with interesting and solid content.
2024年1月18日 16:30
Excellent read, I just passed this onto a friend who was doing a little research on that. And he actually bought me lunch because I found it for him smile So let me rephrase that: Thank you for lunch!
2024年1月19日 15:57
JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic jnanabhumiap.in which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.
2024年1月22日 14:27
온라인 카지노 커뮤니티 온카허브 입니다. 온카허브는 카지노 먹튀 사이트들과 안전한 카지노 사이트 정보를 공유하고 있습니다. 카지노 먹튀검증 전문팀을 자체적으로 운영함으로써 철저한 검증을 진행하고 있습니다.
https://oncahub24.com/
2024年1月22日 15:00
온라인 카지노 커뮤니티 온카허브 입니다. 온카허브는 카지노 먹튀 사이트들과 안전한 카지노 사이트 정보를 공유하고 있습니다. 카지노 먹튀검증 전문팀을 자체적으로 운영함으로써 철저한 검증을 진행하고 있습니다.
2024年1月24日 10:21
카지노사이트 바카라사이트 우리카지노 카지노는 바카라, 블랙잭, 룰렛 및 슬롯 등 다양한 게임을 즐기실 수 있는 공간입니다. 게임에서 승리하면 큰 환호와 함께 많은 당첨금을 받을 수 있고, 패배하면 아쉬움과 실망을 느끼게 됩니다.
2024年1月24日 10:39
하노이 꼭 가봐야 할 베스트 업소 추천 안내 및 예약, 하노이 밤문화 에 대해서 정리해 드립니다. 하노이 가라오케, 하노이 마사지, 하노이 풍선바, 하노이 밤문화를 제대로 즐기시기 바랍니다. 하노이 밤문화 베스트 업소 요약 베스트 업소 추천 및 정리.
2024年1月25日 12:25
베트남 남성전용 커뮤니티❣️ 베트남 하이에나 에서 베트남 밤문화를 추천하여 드립니다. 베트남 가라오케, 베트남 VIP마사지, 베트남 이발관, 베트남 황제투어 남자라면 꼭 한번은 경험 해 봐야할 화끈한 밤문화로 모시겠습니다.
2024年1月25日 12:31
No.1 먹튀검증 사이트, 먹튀사이트, 검증사이트, 토토사이트, 안전사이트, 메이저사이트, 안전놀이터 정보를 제공하고 있습니다. 먹튀해방으로 여러분들의 자산을 지켜 드리겠습니다. 먹튀검증 전문 커뮤니티 먹튀클린만 믿으세요!!