POJ 1236-Network of Schools (图论-有向图强联通tarjan）

题目大意：N(2<N<100)个学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。
问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
问题2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

解题思路：首先用tarjan求得所有强联通分量，将每个强联通分量看成一个点，这样会得到一个有向无环图DAG，那么对于问题一只需要要找出DAG图上有多少个入度为0的点，对于问题二需要在DAG图上找出度为0的点的个数，然后与问题一入度为0的点的个数取最大值，就是问题二的答案。

需要注意的是只有一个强联通分量的时候，需要特判一下。

代码如下：

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 103;

vector<int>vec[N], stk;
bool mp[N][N], in_stk[N];
int low[N], dfn[N], tot, cou_scc;
int belong[N];
int n;

void tarjan(int u, int f)
{
    dfn[u] = low[u] = tot ++;
    stk.push_back(u), in_stk[u] = true;
    for(int i=0; i < vec[u].size(); ++ i)
    {
        int v = vec[u][i];
        if(dfn[v] == -1)
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        ++ cou_scc;
        while(1)
        {
            int v = stk.back();
            stk.pop_back();
            in_stk[v] = false;
            belong[v] = cou_scc;
            if(u == v)
                break;
        }
    }
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        memset(mp, false, sizeof(mp));
        for(int i=1; i<=n; ++ i)
        {
            vec[i].clear();
            int c;
            while(scanf("%d", &c), c)
            {
                vec[i].push_back(c);
                mp[i][c] = true;
            }
        }
        memset(low, -1, sizeof(low));
        memset(dfn, -1, sizeof(dfn));
        memset(belong, -1, sizeof(belong));
        memset(in_stk, false, sizeof(in_stk));
        cou_scc = 0, tot = 1;
        stk.clear();
        for(int i=1; i<=n; ++ i)
        {
            if(dfn[i] == -1)
                tarjan(i, -1);
        }
        int in[N], out[N];
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        for(int i=1; i<=n; ++ i)
        {
            for(int j=1; j<=n; ++ j)
            {
                if(mp[i][j] && belong[i] != belong[j])
                {
                    ++ in[belong[j]];
                    ++ out[belong[i]];
                }
            }
        }
        if(cou_scc == 1)
        {
            printf("1
0
");
            continue;
        }
        int x = 0, y = 0;
        for(int i=1; i<=cou_scc; ++ i)
        {
            if(in[i] == 0)
                ++ x;
            if(out[i] == 0)
                ++ y;
        }
        printf("%d
%d
", x, max(x, y));
    }
}

View Code