Tarjan算法求强连通分量（SCC缩点）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack> 
using namespace std;

struct ss{
    int v;
    int next;
    /*  
    v指节点v 
    next永远指u点->上一个点的边序（1，2，3···）
    边序 即u到其他点（上一个点）是第几条边（num） 
    上一条边没有就是-1 
    */ 
}s[1000]; 

int head[1000];//边序 
int dfn[1000];
int low[1000];
int vis[1000];//相当于栈 
int color[1000];//染色 
int n,m;
int cnt;
int num;
stack<int >st;

void init()
{
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    //memset(color,0,sizeof(color));    
    num=0;
    cnt=0;
}
void add(int u,int v)
{
    s[num].v = v;
    s[num].next = head[u];
    head[u] = num++;
    /*
    将v存进去
    将u->上一个点的边序挂上next
    num一直在++(总边数不会错)
    head[u]更新当前u的边序             
    如果双向再存u挂v边序 
    eg[num].v = u;
    eg[num].next = head[v];
    head[v] = num++;
    */     
}
void Tarjan(int u)
{
    st.push(u);
    dfn[u] = low[u] = ++cnt;//搜索次序号 
    vis[u]=1;//节点x在栈中
    for(int i = head[u]; i != -1; i = s[i].next)
    {
        //通过对u点上一个边序的挂钩
        //构造对连接u点的所有边数遍历查找对应v点 
        int v = s[i].v;
        if(!dfn[v])//不曾访问过 
        {
            Tarjan(v);//找v点 
            low[u] = min(low[u],low[v]);
            /* 
            根节点的dfn值是区分不同环的值
                        low是为了让这个环都等dfn[根]
                        low[根]可能不等dfn[根]
                        根的low继承根的根的dfn 
            1.如果v是根节点
              不论只有v一个点还是有一个环 
              low[v]确实永远比low[u]大(u比v先入)
              v的环low值=dfn[v]都比low[u]的大 
              v不对u产生影响
            2. 
              如果v点与u点成环
              那么顺着v点或v连着的点找下去
              总有一个能连到根节点
              low值回溯的时候继承根的dfn值
                          根的dfn是这个环里面最小的
              low[v]等于dfn[根]
              v对u产生影响->low[u]=low[v] 
            */ 
        }
        else if(vis[v])//访问过但还在栈中 
            /*
            因为根u点还没有将边都找完
            出栈的点都是根节点边已经找完的点或者环 
            已经没有与剩下的点有任何关系才能出 
            */ 
            low[u] = min(low[u],dfn[v]);
            /*
            这相当于根节点有两个分叉口a,b 
            并且a找到已经在栈中的b

            那么这一步其实也可以写成 
            low[u] = min(low[u],low[v]);
                        反正连到一个环了

                        目的是为了让缩点与割点的代码一致 
                        区分相连的环的根有不同的dfn
                        无向图找割点用的
                        但是缩点是将一起出栈的点缩成一个点（染成一个色）
                    对于缩点结果都无影响    
            */
    }    

    if(dfn[u]==low[u])//找一遍再是强连通分量 
    {
        int now;
        do{    //取出包括u的环 
            now=st.top();
            color[now]=u; //染色 
            vis[now]=0;
            st.pop();
        }while(now!=u);
    }
    return;    
} 
void out()
{
    for(int i=1;i<=n;i++)
        printf("%d ",i);
    printf("\n");
    for(int i=1;i<=n;i++)
        printf("%d ",color[i]);
    printf("\n");
}

int main()
{
    while(~scanf("%d%d",&n,&m) && (m+n))
    {
        init();
        int u,v;
        while(m--)
        {
            scanf("%d%d",&u,&v);    
            add(u,v);
        }    
        //为了防止一个图里有不相连的两个或多个树 
        for(int i=1;i<=n;i++) 
            if(!dfn[i]) 
                Tarjan(i);
        out();
    } 
    return 0; 
}