poj1236 Network of Schools【强连通分量（tarjan）缩点】

浏览数：51 / 时间：2015年06月09日

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4316263.html ---by 墨染之樱花

【题目描述】给一张有向图，表示学校通信网络，边<u,v>代表信息可以由u传递到v。现要完成两个任务：1、求最少把几个点作为信息传递的起点就能让信息转达到所有节点 2、最少在添加几条边就能使任意两点间可达（构造强连通分量）

【思路】先利用tarjan缩点使整个图化为DAG新图（有关tarjan的详细资料请戳：https://www.byvoid.com/blog/scc-tarjan/）。

任务一：如果一个点没有入度，那就表示其他点是不可能到达它的，所以该点只能作为一个起点。那么任务一就是等价于求新图中入度为0的点的个数。

任务二：在DAG中从一个没有入度的点（点1）出发，不断地延伸，延伸到一个没有出度的点（点2）时才会停止，此时将点2与点1连接，那么这条路径就会变成一个环，路径各个点就会互相可达。对于整个图来说只要找出所有没入度的点和没出度的点并将它们一一连接就行了，保证每个点都有出度和入度。所以任务二等价于求新图中入度为0的点个数与出度为0的点个数的最大值

#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 110
#define PB(X) push_back(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define CLR(A,X) memset(A,X,sizeof(A))
typedef vector<int> VI;

int V,nV;
VI G[MAXN],nG[MAXN];
int low[MAXN],dfn[MAXN],st[MAXN],belong[MAXN];
int top,cnt,index;
bool inst[MAXN];
int ind[MAXN],outd[MAXN];

void init()
{
    top=cnt=index=0;
    CLR(dfn,0);
    CLR(ind,0);CLR(dfn,0);
}

void tarjan(int u)
{
    low[u]=dfn[u]=++index;
    st[top++]=u;
    inst[u]=1;
    REP(i,G[u].size())
    {
        int v=G[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            if(low[v]<low[u])
                low[u]=low[v];
        }
        else if(inst[v] && dfn[v]<low[u])
            low[u]=dfn[v];
    }
    int j;
    if(low[u]==dfn[u])
    {
        cnt++;
        do
        {
            j=st[--top];
            inst[j]=0;
            belong[j]=cnt-1;
        }while(j!=u);
    }
}

int main()
{
    init();
    scanf("%d",&V);
    REP(i,V)
    {
        int x;
        while(scanf("%d",&x))
        {
            if(x==0)
                break;
            x--;
            G[i].PB(x);
        }
    }
    REP(i,V)
        if(!dfn[i])
            tarjan(i);
    nV=cnt;
    if(nV==1)
    {
        printf("1\n0\n");
        return 0;
    }
    REP(i,V)
    {
        REP(j,G[i].size())
        {
            int x=belong[i],y=belong[G[i][j]];
            if(x!=y)
            {
                nG[x].PB(y);
                ind[y]++;outd[x]++;
            }
        }
    }
    int noInd=0,noOutd=0;
    REP(i,nV)
    {
        if(!ind[i])
            noInd++;
        if(!outd[i])
            noOutd++;
    }
    printf("%d\n%d\n",noInd,max(noInd,noOutd));
    return 0;
}