几道强连通分量模板题（hdu 1269 &）

裸的模板题
把模板分析一下吧，嗯~ o(￣▽￣)o
hdu 1269 迷宫城堡

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;
#define INF 0xffffff
#define MAX 10005
int top;
int Stack[MAX];
bool Instack[MAX];
int DFN[MAX], LOW[MAX];
int Belong;
int Bcnt, Dindex;
vector< vector<int> > G;
int n,m;

void Tarjan(int u)
{
    LOW[u] = DFN[u] = ++Dindex;
    Stack[top++] = u;
    Instack[u] = true;
    int len = G[u].size(),v;
    
    for(int i=0;i<len;i++)
    {
        v = G[u][i];
        if(!DFN[v])
        {
            Tarjan(v);
            LOW[u] = min(LOW[u],LOW[v]);
        }
        else if(Instack[v])
        {
            LOW[u] = min(LOW[u], DFN[v]);
        }
    }
    if(LOW[u] == DFN[u])
    {
        do
        {
            Bcnt++;
            v = Stack[--top];
            Instack[v] = false;
        }while(u != v);
        Belong++;
    }
 } 
 void init()
 {
    G.clear();
    G.resize(n+1);
    memset(LOW,0,sizeof(LOW));
    memset(DFN,0,sizeof(DFN));
    memset(Stack,0,sizeof(Stack));
    memset(Instack,false,sizeof(Instack));
    Bcnt = Belong = Dindex = top = 0;
 }
 
 int main()
 {
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if((n+m) == 0)  break;
        init();
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
        }
        Tarjan(1);
        if(Bcnt == n && Belong == 1)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
     }
 }

HDU - 1827

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stack>
#include<vector>
using namespace std;
const int maxn = 1005;
const int inf = 0xffffff;
int low[maxn],dfn[maxn];
bool vis[maxn];
int cost[maxn];
int tcost[maxn];
int belong[maxn];
int in[maxn],out[maxn];
vector<int > G[maxn];
stack<int >s;
int n,m;
int index,cnt;

void init()
{
    cnt = index = 0;
    for(int i=0;i<=n;i++)
    {
        G[i].clear();
        cost[i] = low[i] = dfn[i] = vis[i] = 0;
        belong[i] = in[i] = out[i] = 0;
        tcost[i] = inf;
    }
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++index;
    vis[u] = true;
    s.push(u);
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]); 
        }
        else if(vis[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        cnt++;
        int x;
        do
        {
            x = s.top();
            s.pop();
            vis[x] = false;
            belong[x] = cnt;
        }while(x!=u);
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cost[i]);
        }    
        for(int i=1;i<=m;i++)
        {
            int u,v; 
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])   Tarjan(i);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<G[i].size();j++)
            {
                int v = G[i][j];
                if(belong[i] != belong[v])
                {
                    out[belong[i]] ++;
                    in[belong[v]] ++;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            tcost[belong[i]] = min(tcost[belong[i]],cost[i]);
        }
        int ans = 0,total = 0;
        for(int i=1;i<=cnt;i++)
        {
            if(in[i] == 0)
            {
                ans++;
                total += tcost[i];
            }
        }
        printf("%d %d\n",ans,total);
    }
    
} 

HDU - 3072