题目链接: 点击打开链接
题意：
给定一个有向图，求：
1) 至少要选几个顶点。才干做到从这些顶点出发，能够到达所有顶点
2) 至少要加多少条边。才干使得从不论什么一个顶点出发，都能到达所有顶点
顶点数<= 100
求完强连通分量后，缩点，计算每一个点的入度，出度。
第一问的答案就是入度为零的点的个数，
第二问就是max(n,m) // 入度为零的个数为n, 出度为零的个数为m. //kuangbin巨巨分析非常棒！
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 100 + 10;
vector<int> G[maxn];
int dfn[maxn], low[maxn], belong[maxn], dfs_clock, scc_cnt;
stack<int> S;
void dfs(int u){
dfn[u] = low[u] = ++dfs_clock;
S.push(u);
for(int i=0; i<G[u].size(); ++i){
int v = G[u][i];
if(!dfn[v]){
dfs(v);
low[u] = min(low[u], low[v]);
}else if(!belong[v]){
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]){
scc_cnt++;
for(;;){
int x = S.top(); S.pop();
belong[x] = scc_cnt;
if(x == u) break;
}
}
}
void find_scc(int n){
dfs_clock = scc_cnt = 0;
memset(belong, 0, sizeof belong );
memset(dfn, 0, sizeof dfn );
for(int i=0; i<n; ++i)
if(!dfn[i]) dfs(i);
}
int main()
{
int n, i, j, x;
scanf("%d", &n);
for(i=0; i<n; ++i)
{
while(scanf("%d",&x),x)
{
x--;
G[i].push_back(x);
}
}
find_scc(n);
if(scc_cnt==1){
printf("1
0
");
return 0;
}
//缩点后，统计每一个点的出度和入度
int in[maxn], out[maxn];
memset(in, 0, sizeof in );
memset(out, 0, sizeof out );
for(i=0; i<n; ++i)
for(j=0; j<G[i].size(); ++j)
{
int v = G[i][j] ;
if(belong[i] != belong[v])
{
out[ belong[i] ]++;
in[ belong[v] ]++;
}
}
int in_tot = 0, out_tot = 0;
for(i=1; i<=scc_cnt; ++i)
{
if(!in[i]) in_tot++;
if(!out[i]) out_tot++;
}
printf("%d
%d
", in_tot,max(in_tot,out_tot));
return 0;
}
/*
by kuangbin
强连通分量缩点求入度为0的个数和出度为0的分量个数
题目大意：N(2<N<100)各学校之间有单向的网络。
每一个学校得到一套软件后。能够通过单向网络向周边的学校传输，
问题1：初始至少须要向多少个学校发放软件，使得网络内全部的学校终于都能得到软件。
2，至少须要加入几条传输线路(边)。使随意向一个学校发放软件后。
经过若干次传送。网络内全部的学校终于都能得到软件。
也就是：
给定一个有向图，求：
1) 至少要选几个顶点，才干做到从这些顶点出发。能够到达全部顶点
2) 至少要加多少条边，才干使得从不论什么一个顶点出发。都能到达全部顶点
顶点数<= 100
解题思路：
1. 求出全部强连通分量
2. 每一个强连通分量缩成一点，则形成一个有向无环图DAG。
3. DAG上面有多少个入度为0的顶点。问题1的答案就是多少
在DAG上要加几条边。才干使得DAG变成强连通的，问题2的答案就是多少
加边的方法：
要为每一个入度为0的点加入入边，为每一个出度为0的点加入出边
假定有 n 个入度为0的点，m个出度为0的点，怎样加边？
把全部入度为0的点编号 0,1,2,3,4 ....N -1
每次为一个编号为i的入度0点可达的出度0点，加入一条出边，连到编号为(i+1)%N 的那个出度0点,
这须要加n条边
若 m <= n，则
加了这n条边后，已经没有入度0点。则问题解决，一共加了n条边
若 m > n。则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，就可以，这还需加m-n条边。
所以，max(m,n)就是第二个问题的解
此外：当仅仅有一个强连通分支的时候，就是缩点后仅仅有一个点，尽管入度出度为0的都有一个，可是实际上不须要添加清单的项了，所以答案是1。0；
*/
/*
input:
30
18 0
7 21 0
1 4 15 28 0
9 0
10 15 16 0
22 26 0
1 5 10 12 0
3 17 29 0
2 5 17 0
19 23 0
20 0
1 7 15 19 0
0
23 0
0
0
5 18 0
0
7 18 0
17 0
24 0
13 21 0
26 0
0
2 23 30 0
2 9 11 13 14 27 0
2 0
14 0
0
28 0
output:
3
6
*/