CUGB图论专场2：J - Network of Schools （Tarjan缩点）

5
2 4 3 0
4 5 0
0
0
1 0

1
2

题意：求（1）至少给多少个结点发消息能使消息传遍整个网络；（消息代指软件，消息传递指软件给别人）

    （2）并进一步求出至少添加多少条边能使对图中任意一个结点发消息都能使消息传遍整个网络。

思路：第一问：我们可以想像一下这个图形，因为是有向图，所以只要在出发点发消息，那么经过传递，整个网络都可以得到消息；出发点在图论中就是入度为0的点嘛！但是在原图中因为出发点可能是一个强连通分量，因为是强连通分量，所以只要在这个强连通分量中的一个结点发一条消息，这个强连通分量中的其他结点就都可以收到消息了，并且经过传递，整个网络就都可以收到消息了，所以一个强连通分量只需要一个结点接收消息就行了，所以需要Tarjan算法缩点后再求入度为0的点。

第二问：因为一个图有出发点（入度为0的点）与终结点（出度为0的点），那么只要把终结点连边到出发点，那么整个图形就都连通了嘛！但是终结点与出发点有大小问题，如果终结点比出发点大的话，那么所有的终结点就都得与出发点连边才能使整个图连通，边数就是终结点的数目；同理出发点比终结点大的话，也要连接所有 的出发点才行，这时边的数目就是出发点的数目。所以总的来说：边的数目=max(出发点数目，终结点数目）。

但是如果原图就是一个强连通图的话，那么出发点就是1个（强连通缩成一个点）；这时需要如边图就是连通了，所以不需要加边了，就是0.

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 10002
#define MN 105
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,cnt,tem,Count,DFN[MN],LOW[MN],od[MN],id[MN],vis[MN],suo[MN],q2[MN];
vector<int>q[MN];//,p[MN]
void tarjan(int u)
{
    int j,v;
    DFN[u]=LOW[u]=++cnt;
    vis[u]=1;
    q2[++tem]=u;
    for(j=0; j<q[u].size(); j++)
    {
        v=q[u][j];
        if(!DFN[v])
        {
            tarjan(v);
            LOW[u]=min(LOW[u],LOW[v]);
        }
        else if(vis[v]&&DFN[v]<LOW[u])
            LOW[u]=DFN[v];
    }
    if(DFN[u]==LOW[u])
    {
        Count++;
        do
        {
            v=q2[tem--];
            vis[v]=0;
            //p[Count].push_back(v);
            suo[v]=Count;
        }
        while(v!=u);
    }
}
void solve()
{
    int v,i,j;
    for(i=1; i<=n; i++)
        if(!DFN[i]) tarjan(i);
    for(i=1; i<=n; i++)
        for(j=0; j<q[i].size(); j++)
        {
            v=q[i][j];
            if(suo[v]!=suo[i])
                od[suo[i]]++,id[suo[v]]++;
        }
}
//void init()
//{
//    Count=cnt=tem=0;
//    mem(DFN,0);
//    mem(od,0);
//    mem(LOW,0);
//    mem(vis,0);
//    mem(suo,0);
//}
int main()
{
    sca(n);
    int u,v,sum1=0,sum2=0;
    for(u=1;u<=n;u++)
    {
        while(sca(v)&&v)
            q[u].push_back(v);
    }
    solve();
    for(u=1;u<=Count;u++)
    {
        if(id[u]==0) sum1++; //入度点数
        if(od[u]==0) sum2++; //出度点数
    }
    sum2=max(sum1,sum2);
    if(Count==1) sum1=1,sum2=0; //原图就是连通图
    cout<<sum1<<endl<<sum2<<endl;
    return 0;
}

CUGB图论专场2：J - Network of Schools （Tarjan缩点）

原文：http://blog.csdn.net/u011466175/article/details/19497649