poj1236 Network of Schools ，求强连通分量（Tarjan算法），缩点

题目链接: 点击打开链接

题意：

 给定一个有向图，求：
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\n0\n");
        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\n%d\n", 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
*/

poj1236 Network of Schools ，求强连通分量（Tarjan算法），缩点,古老的榕树,5-wow.com