そして調査集(hrbust oj 1160吸血鬼)

そして、私は連絡のある数を解決する時、とても使いやすいと思います.例えば、感染、接触、感染者を通じて、感染人数を計算する必要があります.これは典型的な調査問題です.例えば次の問題は吸血鬼です
クリックしてリンクを開く
吸血鬼0は最も原始的なルートノードであり、それに接触された人は偽吸血鬼になり、彼の子ノードであり、偽吸血鬼が接触した人は偽吸血鬼の子ノードとなり、このように人に接触しないまで往復することができる.
この問題は、すべての吸血鬼の個数を計算するには、一人一人のルートノードを検索するだけで、0かどうか、つまり真の吸血鬼を検索する必要があります.
ルートノードを探すコードは次のように実現されます.

int findd(int x) //  x    
{
    int r=x;
    while(r!=pre[r]) //per[r] r    ， r         ，        。
        r=pre[r]; //   r     ，  ， r       ，        ，       。
    return r;//     
}

ルートノードを探す以外に、2つの数に親子関係を持たせることも重要な操作であり、コードは以下のように実現される.

void mix(int x,int y)  //  x，y      ，     ，  x,y     
{
    int fx=findd(x),fy=findd(y);  //  x，y    
    if(fx!=fy)  //           ，        
    {
        pre[fy]=fx; //      ，   fx  fy   （          ，          ）
    }
}

そしてセットの2組の重要な操作を調べて完成して、以下のテーマは簡単にコードで実現します
MACコードは以下の通り

#include
#include
#include
#include
#include
#include
using namespace std;
int pre[10005];
int b[10005];
int findd(int x)
{
     int r=x;
    while(r!=pre[r])
        r=pre[r];
        return r;
}
void mix(int x, int y)
{
    int fx = findd(x);
    int fx = findd(y);
    if(fx!=fy)
        pre[fx] = fy;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))

    {
        if(n==0&&m==0) break;
        for(int i = 0; i < n; i++)
        pre[i] = i;    //          ，           
    while(m--)
    {
        int k,x,y;
        scanf("%d",&k);
        for(int i = 0; i < k; i++)
        {
            scanf("%d",&b[i]);
            if(i > 0)
            {
                int a = findd(b[i]);
                int k = findd(b[i-1]);
                mix(a,k);
            }
        }
    }
    int ans = findd(0),count = 0;
    for(int i = 0; i < n; i++)
        {
            if(findd(i)==ans) count++; //         0，         
        }
        printf("%d
",count);
    }


}