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

题目链接：http://poj.org/problem?id=1236

题目大意：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 = ;

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=; i < vec[u].size(); ++ i)

    {

        int v = vec[u][i];

        if(dfn[v] == -)

        {

            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()

        {

            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=; i<=n; ++ i)

        {

            vec[i].clear();

            int c;

            while(scanf("%d", &c), c)

            {

                vec[i].push_back(c);

                mp[i][c] = true;

            }

        }

        memset(low, -, sizeof(low));

        memset(dfn, -, sizeof(dfn));

        memset(belong, -, sizeof(belong));

        memset(in_stk, false, sizeof(in_stk));

        cou_scc = , tot = ;

        stk.clear();

        for(int i=; i<=n; ++ i)

        {

            if(dfn[i] == -)

                tarjan(i, -);

        }

        int in[N], out[N];

        memset(in, , sizeof(in));

        memset(out, , sizeof(out));

        for(int i=; i<=n; ++ i)

        {

            for(int j=; j<=n; ++ j)

            {

                if(mp[i][j] && belong[i] != belong[j])

                {

                    ++ in[belong[j]];

                    ++ out[belong[i]];

                }

            }

        }

        if(cou_scc == )

        {

            printf("1\n0\n");

            continue;

        }

        int x = , y = ;

        for(int i=; i<=cou_scc; ++ i)

        {

            if(in[i] == )

                ++ x;

            if(out[i] == )

                ++ y;

        }

        printf("%d\n%d\n", x, max(x, y));

    }

}