POJ 1611

The Suspects

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.
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.
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
1
題意:
0是公認(rèn)的懷疑人资盅,和他一組的也算是懷疑人举哟,被懷疑的一組的人在其他組耕腾,那么他們也變成懷疑人了筋现。
思路:聯(lián)通塊問(wèn)題悟衩,把一個(gè)組的連一起,組里的人在其他組惠昔,也連起來(lái)挑势。然后找和0連起來(lái)的人。

#include<stdio.h>
int s1[30005];
int find(int x)
{
    if(x==s1[x])
    return x;
    else
    return s1[x]=find(s1[x]);
}
int main()
{
    int n,m,i,j,s,count,t,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
        break;
            for(i=0;i<=n;i++)
        {
            s1[i]=i;
        }
    
        for(i=0;i<m;i++)
        {
            scanf("%d",&t);
            scanf("%d",&x);     //把一個(gè)組連在一起
            
                for(j=1;j<t;j++)
                {
                    scanf("%d",&y);
                    x=find(x);
                    y=find(y);
                    if(x!=y)
                    {
                        s1[x]=y;
                    }
                }
            
        }
        s=find(0);
        count=0;
        for(j=0;j<n;j++)
        {
            if(s==find(j))     //找和0連起來(lái)的數(shù)字
            {
                count++;
            }
        }
        printf("%d\n",count);   
    }
} 
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市饼齿,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌考传,老刑警劉巖僚楞,帶你破解...
    沈念sama閱讀 211,743評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異泉褐,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)挺邀,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門端铛,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)疲眷,“玉大人,你說(shuō)我怎么就攤上這事换淆∶勒欤” “怎么了?”我有些...
    開封第一講書人閱讀 157,285評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵耻煤,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我哈蝇,道長(zhǎng),這世上最難降的妖魔是什么怜跑? 我笑而不...
    開封第一講書人閱讀 56,485評(píng)論 1 283
  • 正文 為了忘掉前任性芬,我火速辦了婚禮剧防,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘俊庇。我一直安慰自己,他們只是感情好辉饱,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,581評(píng)論 6 386
  • 文/花漫 我一把揭開白布止后。 她就那樣靜靜地躺著,像睡著了一般译株。 火紅的嫁衣襯著肌膚如雪挺益。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,821評(píng)論 1 290
  • 那天匪补,我揣著相機(jī)與錄音夯缺,去河邊找鬼甘耿。 笑死,一個(gè)胖子當(dāng)著我的面吹牛佳恬,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播毁葱,決...
    沈念sama閱讀 38,960評(píng)論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼筷频,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了凛捏?” 一聲冷哼從身側(cè)響起际度,我...
    開封第一講書人閱讀 37,719評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤坡锡,失蹤者是張志新(化名)和其女友劉穎蓬网,沒(méi)想到半個(gè)月后帆锋,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體锯厢,經(jīng)...
    沈念sama閱讀 44,186評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡脯倒,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,516評(píng)論 2 327
  • 正文 我和宋清朗相戀三年藻丢,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了悠反。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,650評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡梨水,死狀恐怖茵臭,靈堂內(nèi)的尸體忽然破棺而出笼恰,到底是詐尸還是另有隱情,我是刑警寧澤,帶...
    沈念sama閱讀 34,329評(píng)論 4 330
  • 正文 年R本政府宣布追葡,位于F島的核電站奕短,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏谬返。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,936評(píng)論 3 313
  • 文/蒙蒙 一佑刷、第九天 我趴在偏房一處隱蔽的房頂上張望酿炸。 院中可真熱鬧,春花似錦填硕、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至周荐,卻和暖如春概作,著一層夾襖步出監(jiān)牢的瞬間默怨,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留痕檬,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,370評(píng)論 2 360
  • 正文 我出身青樓丘跌,卻偏偏與公主長(zhǎng)得像闭树,于是被迫代替她去往敵國(guó)和親报辱。 傳聞我的和親對(duì)象是個(gè)殘疾皇子单山,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,527評(píng)論 2 349

推薦閱讀更多精彩內(nèi)容

  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,435評(píng)論 0 23
  • 秋鸵赫,吹落最后一片樹葉 樹葉帶著思戀,飄啊飄啊 穿過(guò)叢林狼忱,越過(guò)小溪 飄落在少年的那雙白球鞋上 少年拾起樹葉 看著遠(yuǎn)方...
    南城舊館閱讀 145評(píng)論 2 1
  • 01“你覺(jué)得嫁給愛(ài)情是種什么體驗(yàn)?”21歲的表妹躺著沙發(fā)上悶悶地問(wèn)我一睁。這是她失戀后第57次向我發(fā)問(wèn)钻弄,之前還問(wèn)過(guò)“怎...
    冷愛(ài)閱讀 261評(píng)論 0 0
  • 緊合雙目卻比睜眼現(xiàn)實(shí),炯炯圓睜又如蒙閉愚昧者吁,或許窘俺,就是文人和其他人的區(qū)別。 人們活在當(dāng)下复凳,就好比一場(chǎng)恢宏的即興表演...
    吾欲閱讀 251評(píng)論 0 1
  • 權(quán)謀從哪來(lái)瘤泪? 有位網(wǎng)友問(wèn)了我2個(gè)問(wèn)題,什么樣的公司不玩權(quán)術(shù)育八?為什么30歲了發(fā)現(xiàn)自己慫了对途? 我發(fā)現(xiàn)只有一種人,無(wú)需玩...
    諸葛司馬村夫閱讀 349評(píng)論 0 0