【并查集】資料結構與算法實驗題 11.2 病毒排查問題

資料結構與算法實驗題 11.2 病毒排查問題

★ 問題描述 :

最近，網絡中心發現了一種傳播能力很強的病毒。如果一台計算機感染了 這

種病毒，那麼它可以通過網絡傳播到其它與其相聯的計算機中。

現在，網絡中心為了阻止這種病毒的傳播，打算找出所有可能感染此病毒 的

計算機，并對這些計算機進行處理。我們假設如果一個網絡中有一台計算機感 染

了此病毒，那麼該網絡中的其它計算機都有可能感染此病毒。現在給你各個網 絡

的資訊，要你找出有可能感染此病毒的計算機總數。

★ 實驗任務：

為了簡化問題，我們假設學校有 N 台計算機，編号為 0 到 N - 1 ， 0 号已确 定

感染了此病毒。接下給出每個網絡中的計算機資訊。注意，一台計算機可能同 時

加入好幾個網絡。現在要求你求出可能感染此病毒的計算機數目（包含已感染 的

0 号計算機）。

★ 資料輸入：

由檔案 input.txt 給出輸 入。 第一 行包 含兩 個數 N(0<N<=30000) 與

M(0<=M<=500) ，表示有 N 台計算機， M 個網絡。接下來 M 行，每行包含一個

網絡資訊。每行的第一個整數 K 表示這個網絡中有 K 台計算機，接下來 K 個 數

Ki(1<=i<=k) 表示該網絡中的計算機編号 (1<=K<=N,0<=Ki<N) 。

★ 結果輸出 :

一個整數 X ，表示可能感染病毒的計算機的總數。輸出到 output.txt 。

輸入示例 輸出示例

input.txt

100 4

2 1 2

5 10 13 11 12 14

2 0 1

2 99 2

output.txt

4

第一次做并查集的題目。。。。。

本題要注意的是需要記錄每個集合的節點個數，需要另外開一個數組來存儲。 

#include <stdio.h>

#define NUMOFPOINT 30000

int parent[NUMOFPOINT]; //初始化為下标

int deep[NUMOFPOINT]; //初始化為1

int NumOfPoint[NUMOFPOINT]; //記錄各棵樹的節點個數，初始化為1

int Find(int n)

{

while (parent[n] != n)

n = parent[n];

return n;

}

int Union(int a, int b)

{

int ParientA;

int ParientB;

ParientA = Find(a);

ParientB = Find(b);

if (ParientA == ParientB)

return ParientA;

if (deep[ParientA]>deep[ParientB])

{

parent[ParientB] = ParientA;

NumOfPoint[ParientA] += NumOfPoint[ParientB];

return ParientA;

}

else

{

parent[ParientA] = ParientB;

NumOfPoint[ParientB] += NumOfPoint[ParientA];

if (deep[ParientA] == deep[ParientB])

deep[ParientB]++;

return ParientB;

}

}

void Init(int n)

{

int i;

for (i=0;i<n;i++)

{

deep[i] = 1;

parent[i] = i;

NumOfPoint[i] = 1;

}

}

int main()

{

int n,m,c,c1,i,k,j,un,un0;

while (scanf("%d%d", &n, &m)!=EOF)

{

Init(n);

for (i=0;i<m;i++)

{

scanf("%d", &k);

scanf("%d", &c);

un = c;

for (j=0;j<k-1;j++)

{

scanf("%d", &c1);

un = Union(un, c1);

}

}

un0 = Find(0);

printf("%d/n", NumOfPoint[un0]);

}

return 0;

}