poj 1236 Network of Schools（连通图）

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

题目大意：有一些学校，学校之间可以进行收发邮件，给出学校的相互关系，问：1.至少

要向这些学校发送多少份才能使所有的学校都能获得邮件；2.若想只发送一份即可让所有学

校都能收到邮件，则至少需要需要再进行多少次学校之间的连接。

学校之间的关系可构成图，将图进行强连通缩点成块儿后可知，每个进入数为0的点需要发

送一份；若想要所有点都连接，则需要连接数目为max（入度为0点数，出度为0点数），这

个是结论，详细证明不再贴。

代码如下：

/**

Memory: 604K        Time: 16MS
Language: G++        Result: Accepted

**/
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
vector<int>G[110];
int n, Stack[110], low[110], dfn[110], Time, Top, nblocks, belong[110], inStack[110];
int in[110], out[110];
void Init()
{
    for(int i=1; i<=n; i++)
    {
        G[i].clear();
        low[i] = dfn[i] = in[i] = out[i] = inStack[i] = belong[i] = 0;
    }
    Time = Top = nblocks = 0;
}
void Tarjin(int u)
{
    low[u] = dfn[u] = ++Time;
    Stack[Top++] = u;
    inStack[u] = 1;
    int v, len = G[u].size();
    for(int i=0; i<len; i++)
    {
        v = G[u][i];
        if(!dfn[v])
        {
            Tarjin(v);
            low[u] = min(low[u], low[v]);
        }
        else if(inStack[v])
            low[u] = min(low[u], dfn[v]);
    }

    if(low[u]==dfn[u])///强连通缩点
    {
        nblocks++;
        do
        {
            v = Stack[--Top];
            inStack[v] = 0;
            belong[v] = nblocks;
        }
        while(u!=v);
    }
}
int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        Init();
        int x;
        for(int i=1; i<=n; i++)
        {
            while(scanf("%d", &x), x)
                G[i].push_back(x);
        }
        for(int i=1; i<=n; i++)
        {
            if(!dfn[i])
                Tarjin(i);
        }
        for(int i=1; i<=n; i++)
        {
            int len = G[i].size();
            for(int j=0; j<len; j++)///标记缩点后的出入度
            {
                int u = belong[i];
                int v = belong[G[i][j]];
                if(u!=v)
                {
                    out[u]++;
                    in[v]++;
                }
            }
        }
        int in_zero_num = 0;
        int out_zero_num = 0;
        for(int i=1; i<=nblocks; i++)
        {
            if(!in[i])in_zero_num++;
            if(!out[i])out_zero_num++;
        }
        if(nblocks==1)
        {
            printf("1
0
");
            continue;
        }
        printf("%d
%d
", in_zero_num, max(in_zero_num, out_zero_num));
    }
    return 0;
}

/**

唐僧师徒四人一起去取经，沙僧是个细心的人，一路上照顾师徒四人的饮食起居，

这天他在整理大师兄的内裤，发现有个洞，然后就耐心的缝了起来，第二天发现

又有个洞，于是又补了起来，第三天依旧还是有个洞，正当他拿起针线时，猴哥

过来，一脚踹飞了沙僧。尼玛，把洞缝上，尾巴搁哪儿？

**/