校园网络
时间限制:3000 ms | 内存限制:65535 KB
难度:5
南阳理工学院共有M个系,分别编号1~M,其中各个系之间达成有一定的协议,如果某系有新软件可用时,该系将允许一些其它的系复制并使用该软件。但该允许关系是单向的,即:A系允许B系使用A的软件时,B未必一定允许A使用B的软件。
现在,请你写一个程序,根据各个系之间达成的协议情况,计算出最少需要添加多少个两系之间的这种允许关系,才能使任何一个系有软件使用的时候,其它所有系也都有软件可用。
每组测试数据的第一行是一个整数M,表示共有M个系(2<=M<=100)。
随后的M行,每行都有一些整数,其中的第i行表示系i允许这几个系复制并使用系i的软件。每行结尾都是一个0,表示本行输入结束。如果某个系不允许其它任何系使用该系软件,则本行只有一个0.
1 5 2 4 3 0 4 5 0 0 0 1 0
2
思路:
强连通分量缩点后,再找入度为0的节点数 和 出度为0的节点数 的最大值即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <vector> using namespace std; const int VMAX = 105; int in[VMAX], out[VMAX]; vector<int> G[VMAX]; int n; int dfs_clock, scc_cnt; int pre[VMAX], cmp[VMAX], low[VMAX]; stack<int> s; void dfs (int u) { low[u] = pre[u] = ++dfs_clock; s.push(u); for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if (!pre[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if (!cmp[v]) { low[u] = min(low[u], pre[v]); } } if (pre[u] == low[u]) { ++scc_cnt; for ( ;;) { int x = s.top(); s.pop(); cmp[x] = scc_cnt; if (x == u) break; } } } void scc() { scc_cnt = dfs_clock = 0; memset(cmp, 0, sizeof(cmp)); memset(pre, 0, sizeof(pre)); for (int i = 1; i <= n; ++i) { if (!pre[i]) dfs(i); } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { G[i].clear(); in[i] = out[i] = 0; } for (int i = 1; i <= n; ++i) { int num; while (~scanf("%d", &num) && num) { G[i].push_back(num); } } scc(); for (int i = 1; i <= n; ++i) { for (int j = 0; j < G[i].size(); ++j) { int v = G[i][j]; ++in[ cmp[v] ]; ++out[ cmp[i] ]; } } int in_num = 0, out_num = 0; for (int i = 1; i <= scc_cnt; ++i) { if (!in[i]) ++in_num; if (!out[i]) ++out_num; } printf("%d\n", max(in_num, out_num)); } return 0; }
相关推荐
实现了求一个有向图的强连通分量,并把分量输出到文件中。
强连通分量函数.c
求强连通分量 有向图 求强连通分量 有向图 求强连通分量 有向图 求强连通分量 有向图
强连通分量Kosaraju算法和缩点法的教学ppt
使用Tarjan算法进行快速计算强连通分量,C++语言实现。
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
有向图的强连通分量课程设计报告
2. 用Kosaraju算法实现了强连通分量的求解。其中data中包含的GoolNodes测试集为Google提供的网页之间的连接经转化而来,每一个结点均代表一个网页。 3. 缺点:为了使用以前的CGraph类,强行添加了结点文件,其中第一...
trajan gabow Kosaraju 双连通分量和强连通分量 希望对大家有助
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
用python求取强连通分量个数 假设我们有一个有向图,其顶点和边如下所示: 顶点:0,1,2,3,4,5,6,7 边:(0→1,(1→2),(2→0),(2→3),(3→4),(4→5),(5→3),(5→6),(6→4),(6→7) 接下来,我将编写一个...
无向图的强连通分量(1).cpp //这个是内网比赛的代码,用到了无向图的双连通分量 ,gabow部分是求双联通的
求有向图的强连通分量(scc)Tarjan算法.docx
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
十字链表可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧有一个结点,对应于每一个顶点也有一个结点。然后建立有向图,然后利用深度优先遍历求解强连通分量
强连通分量个数怎么求?用小白都能理解的C语言去解答这个问题最合适不过。 原理熟悉,深度搜索,小白入手无压力 强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组...
在键盘上输入有向图,对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图,求出该图的所有强连通分量并输出字符
要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建立好的图进行深度和广度优先遍历。具体实现要求: 1. 通过键盘输入图的顶点...3. 统计两个图的连通分量的个数。
图论中一个图序列强连通分量的检测程序,属于datastructure,帮助搜索算法