POJ 1236 Network of Schools 连通图缩点

题目大意：有向图连通图，第一问求至少需要多少个软件才能传输到所有学校，第二问求至少需要增加多少条路使其成为强连通图

题目思路：利用Tarjan算法经行缩点，第一问就是求缩点后入度为0的点的个数（特殊情况，当缩点后仅剩一个点是输出0），第二问就是求缩点后max（入度为0的点的个数，出度为0的点的个数）。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAXSIZE 105
#define LL long long

using namespace std;

int Stuck[MAXSIZE],vis[MAXSIZE],dfn[MAXSIZE],low[MAXSIZE],belong[MAXSIZE],in[MAXSIZE],out[MAXSIZE],block,k,Time,e,n,Map[MAXSIZE][MAXSIZE];

void Tarjan(int u)
{
    dfn[u]=low[u]=++Time;//时间戳
    Stuck[++k]=u;
    vis[u]=1;
    for(int i=1;i<=n;i++)
    {
        if(!Map[u][i]) continue;
        if(!dfn[i])
        {
            Tarjan(i);
            low[u]=min(low[u],low[i]);
        }
        else if(vis[i])
        {
            low[u]=min(low[u],dfn[i]);
        }
    }
    if(low[u]==dfn[u])
    {
        int temp;
        do{
            temp=Stuck[k--];
            belong[temp]=block;//记录该点属于哪个“块”
            vis[temp]=0;
        }while(u!=temp);
        block++;//更新“块”数
    }
}

int main()
{
    int a;
    while(scanf("%d",&n)!=EOF)
    {
        memset(Map,0,sizeof(Map));
        memset(vis,0,sizeof(vis));
        memset(belong,0,sizeof(belong));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        Time=0;
        block=1;
        k=0;
        for(int i=1;i<=n;i++)
        {
            while(scanf("%d",&a),a)
            {
                Map[i][a]=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                Tarjan(i);
            }
        }
        for(int i=1;i<=n;i++)//缩点过程
        {
            for(int j=1;j<=n;j++)
            {
                if(!Map[i][j]) continue;
                if(belong[i]!=belong[j])//i,j分别属于不同的“块”，且i到j有路径，那么i所在“块”的出度加一，j所在“块”的入度加一
                {
                    out[belong[i]]++;
                    in[belong[j]]++;
                }
            }
        }
        int sum_in=0;
        int sum_out=0;
        for(int i=1;i<block;i++)
        {
            if(!in[i]) sum_in++;
            if(!out[i]) sum_out++;
        }
        int ans=max(sum_in,sum_out);//两者最大值即为需新增的路径数
        if(block==2)
            printf("1
0
");
        else
            printf("%d
%d
",sum_in,ans);
    }
    return 0;
}