Network of Schools
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 10516 | Accepted: 4196 |
Description
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
Input
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
Sample Input
5 2 4 3 0 4 5 0 0 0 1 0
Sample Output
1 2
题意:
给出 N,代表有 N(2 ~ 100) 个结点,后给出 N 行,每行 i 都给出一系列的节点编号 j ,代表 i 到 j 有一条单向边,直到输入 0 时候退出。输出两个数,第一个数是问最少需要向多少个点发送信息,能使这个信息能到达所有的点,第二个数是需要增加多少条单向边,使这个图任意两点间都能互相到达。
思路:
强连通分量。先对图进行强连通缩点后变成一个 DAG ,第一个数即找多少个入度为 0 的点。第二个数找的是 入度为 0 的点的个数 和 出度为 0 的点的个数 的最大值。需要注意的是,当这个图本身就是个强连通分量的话要另外讨论,输出的是 1 和 0 。
AC:
#include <iostream> #include <cstdio> #include <cstring> #include <stack> using namespace std; const int NMAX = 105; const int EMAX = 105 * 105; int n, ind; int fir[NMAX], Next[EMAX], v[EMAX]; int dfs_clock, scc_cnt; int cmp[NMAX], low[NMAX], pre[NMAX]; stack<int> s; int nscc[NMAX][NMAX], in[NMAX], out[NMAX]; void add_edge(int f, int t) { v[ind] = t; Next[ind] = fir[f]; fir[f] = ind; ++ind; } void dfs(int u) { pre[u] = low[u] = ++dfs_clock; s.push(u); for (int e = fir[u]; e != -1; e = Next[e]) { if (!pre[ v[e] ]) { dfs( v[e] ); low[u] = min(low[u], low[ v[e] ]); } else if (!cmp[ v[e] ]) { low[u] = min(low[u], pre[ v[e] ]); } } if (low[u] == pre[u]) { ++scc_cnt; for (;;) { int x = s.top(); s.pop(); cmp[x] = scc_cnt; if (x == u) break; } } } void scc() { dfs_clock = scc_cnt = 0; memset(cmp, 0, sizeof(cmp)); memset(pre, 0, sizeof(pre)); for (int u = 1; u <= n; ++u) { if (!pre[u]) dfs(u); } } void make_scc() { memset(nscc, 0, sizeof(nscc)); memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); for (int f = 1; f <= n; ++f) { for (int e = fir[f]; e != -1; e = Next[e]) { int t = v[e]; if (cmp[f] != cmp[t] && !nscc[ cmp[f] ][ cmp[t] ]) { nscc[ cmp[f] ][ cmp[t] ] = 1; ++in[ cmp[t] ]; ++out[ cmp[f] ]; } } } } int main() { ind = 0; memset(fir, -1, sizeof(fir)); scanf("%d", &n); for (int f = 1; f <= n; ++f) { int t; while (~scanf("%d", &t) && t) { add_edge(f, t); } } scc(); make_scc(); int temp = 0; for (int i = 2; i <= n; ++i) { if (cmp[i] != cmp[i - 1]) { temp = 1; break; } } if (temp) { int in_num = 0, out_num = 0; for (int i = 1; i <= scc_cnt; ++i) { if (!out[i]) ++out_num; if (!in[i]) ++in_num; } printf("%d\n%d\n", in_num, max(out_num, in_num) ); } else printf("1\n0\n"); return 0; }
相关推荐
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
求有向图的强连通分量(scc)Tarjan算法.docx
使用Tarjan算法进行快速计算强连通分量,C++语言实现。
图论- 图的连通性- Tarjan 求强连通分量.rar
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
纯代码
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
以下是使用C语言实现查找强连通分量的示例代码,基于深度优先搜索(DFS)算法和Tarjan算法: 在上面的示例中,我们使用邻接矩阵来表示有向图。tarjan()函数是整个算法的入口,它会遍历所有节点并调用findSCCs()函数...
Tarjan+R.E.+Data+structures+and+network+algorithms
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
Tarjan求有向图的强连通分量, */ #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 10; struct Edge{ int to, next, dis; }edge[MAXN << 1];
图论- 图的连通性- Tarjan 求双连通分量.rar
Tarjan割点割边,强联通分量讲解
图论- 图的连通性- Tarjan 缩点.rar
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
Tarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms.pdfTarjan-data_structures_and_network_algorithms....
图论- 图的连通性- Tarjan 求割点与桥.rar