【poj 1236 Network of Schools】(強連通成分,Tarjanアルゴリズム縮点)

Tarjanアルゴリズム:http://blog.csdn.net/feng_zhiyu/article/details/78941782題意:N台のパソコンの間で有向辺(u,v)を通じてu台目のパソコンからv台目のパソコンにファイルを転送することができる.u台目のパソコンにファイルを投入すれば、このファイルはv台目のパソコンに転送され、N台のパソコンの接続状況を与えることができます.1、少なくともこのN台のパソコンの中の何台かのパソコンにファイルを投入すれば、N台のパソコンがファイルを受信できるようになります.2、少なくともこのN台のコンピュータで構成された図にいくつかの辺を追加して、1台のコンピュータにファイルを投入するだけで、N台のコンピュータがすべてファイルを受信することができるようにします.
分析:問題1:有向無ループ図では、エッジが強い連通成分間のファイル転送関係に変化する.すなわち,縮点後入度0の点の個数を求める.問題2:有方向無環図を強連通成分に変換する.つまり、縮み点を求めると入度が0と出度が0の2つの最大値注意:縮み点が1つしかない場合、答えは1 0です

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define mem(a,n) memset(a,n,sizeof(a))
#define memc(a,b) memcpy(a,b,sizeof(b))
#define rep(i,a,n) for(int i=a;i///[a,n)
#define dec(i,n,a) for(int i=n;i>=a;i--)///[n,a]
#define pb push_back
#define fi first
#define se second
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-1.0);
const double E=2.718281828459045;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int MOD=258280327;
const int N=1e2+5;
const ll maxn=1e6+5;
const int dir[4][2]= {-1,0,1,0,0,-1,0,1};
int ans[N],dfn[N],low[N];
int vis[N],sta[N],color[N];
int in[N],out[N];
int n,m,scc,cnt,tail;
vector<int>g[N];
void init()
{
    cnt=1;///     
    scc=0;///        
    tail=0;///     
    mem(in,0);
    mem(out,0);
    mem(low,0);
    mem(dfn,0);
    mem(vis,0);
    for(int i=0; i<=n; i++) g[i].clear();
}
void tarjan(int u)
{
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    sta[++tail]=u;
    for(int i=0; iint v=g[u][i];
        if(vis[v]==0) tarjan(v);///  v       
        if(vis[v]==1) low[u]=min(low[u],low[v]);///  v     
    }
    if(dfn[u]==low[u]) ///          
    {
        scc++;
        do ///  
        {
            low[sta[tail]]=scc;
            color[sta[tail]]=scc;///    
            vis[sta[tail]]=-1;
        }
        while(sta[tail--]!=u);
    }
}
void solve()///          
{
    for(int i=1; i<=n; i++)///     
    {
        if(!vis[i]) tarjan(i);
    }
    for(int i=1; i<=n; i++)
        for(int j=0; jif(color[i]!=color[g[i][j]])///           
            {
                out[color[i]]++;
                in[color[g[i][j]]]++;
            }
        }
    int ans1=0,ans2=0;
    for(int i=1; i<=scc; i++)///         
    {
        if(in[i]==0) ans1++;
        if(out[i]==0) ans2++;
    }
    if(scc==1) printf("1
0
");
    else printf("%d
%d
",ans1,max(ans1,ans2));
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        for(int i=1; i<=n; i++)
        {
            while(scanf("%d",&m)&&m)
                g[i].push_back(m);
        }
        solve();
    }
    return 0;
}