2 hardo jan waldotch Hardo_Jan_Waldotch 于 2016.09.15 17:43 提问

c语言编程:安全网络问题

在一个网络中,我们称服务器S是关键服务器,如果至少有另两部不同的服务器A和B,而A与B之间是所有联络都通过S。即若S崩溃,则A与B之间不能进行通讯。如果一个网络不包含关键服务器,则称它是安全的。服务器间所有的联络都是双向的,且一个服务器不允许直接与自身相联。网络中可以存在单机和子网。
要求写一个程序,找出一个给定的网络分割,使其拥有数量最少的安全子网。

第一行只包含一个正整数n,表示网络中服务器的台数。
以下有n行,每行表示一个服务器的连接状况。在每行中,第一个数k表示是第k号服务器(0≤k≤n-1),第二个数是用括号括起来的(该数与括号之间没有空格)表示与该服务器直接相连的服务器的数目;剩下的是与该服务器直接相连的服务器的号数。服务器的号数是用0到n-1的整数表示;相邻数据之间至少用一个空格隔开。

第一行表示安全子网的最少个数。以下每行代表一个子网,每个子网内的服务器按号数升序排列,每个服务器号数间用单个空格分隔。按每个子网中最小的服务器的号数,由小到大排列子网。

Sample Input
8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)

Sample Output
5
0 1
1 2 3
3 4
5
6 7

100%的数据:n≤100

1个回答

Hardo_Jan_Waldotch
Hardo_Jan_Waldotch   2016.09.15 17:54
已采纳

好像与tarjan求scc有关(强连通通分量)

Csdn user default icon
上传中...
上传图片
插入图片