【并查集】数据结构与算法实验题 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;

}