Hardo_Jan_Waldotch 2016-09-15 09:43 采纳率: 100%
浏览 1215
已采纳

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 2016-09-15 09:54
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料