校园网络（强连通分量）

校园网络

时间限制：3000 ms  |  内存限制：65535 KB

难度：5

 

描述

南阳理工学院共有M个系，分别编号1~M,其中各个系之间达成有一定的协议，如果某系有新软件可用时，该系将允许一些其它的系复制并使用该软件。但该允许关系是单向的，即：A系允许B系使用A的软件时，B未必一定允许A使用B的软件。

现在，请你写一个程序，根据各个系之间达成的协议情况，计算出最少需要添加多少个两系之间的这种允许关系，才能使任何一个系有软件使用的时候，其它所有系也都有软件可用。

 

输入

第一行输入一个整数T，表示测试数据的组数(T<10)
每组测试数据的第一行是一个整数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;
}