极大强连通分量Tarjan算法

[UNICKCHENG]

极大强连通分量Tarjan算法

带更新题库

[任务] 给定一个有向图,找出图中的极大强联通分量,并将属于同一个强联通分量内的点染同样的颜色 [说明] dfn[i]记录的是节点i在深度优先遍历中的访问次序 low[i]记录的是点i可以到达的访问时间最早的祖先 Stack是记录节点的栈 深度优先遍历整个图,一路上标记dfn并把新节点压入栈中.对于一个节点i,如果它的dfn和low值相等,说明它无法到达它任何一个祖先.而在栈里面i与i之后的点一定是能够与i互达的(否则之前就会被弹出栈),所以i与栈里i之后的点形成一个极大强连通分量.这一部分可以作为整体弹出. [接口] struct strongly_connecterd_components 复杂度:O(|v|+|E|)

struct strongly_connecterd_components
{
vector<int>&color;
vector<int> Stack;
int colorCnt,curr,*instack,*dfn,*low,*inf,*next,*to;

vodi dfs(int x)
{
    dfn[x]=low[x]=++cur;
    Stack.push_back(x);
    instack[x]=true;
    for(int j=info[x];j;j=next[j])
    {
        if(!instack[to[j]])
        {
            dfs(to[j]);
            low[x]=std:min(low[x],low[to[j]]);
        }
        else 
        {
            if(instack[to[j]]==1)low[x]=std:min(low[x],dfn[to[j]]);
        }
    }
    if(low[x]==dfn[x])
    {
        while(Stack.back()!=x)
        {
            color[Stack.back()]=colorCnt;
            instack[Stack.back()]=2;
            Stack.pop_back();
        }
        color[Stcak.back()]=colorCnt++;
        instack[Stack.back()]=2;
        Stack.pop_back();
    }
}
strongly_connecterd_components(const std::vector<std::pair<int,int>> &edgeList,int n,std::vector<int>&ans):color(ans)
{
    color.resize(n);
    instack=new int[n];
    dfn=new int[n];
    low=new int[n];
    info=new int[n];
    next=new int[(int)edgeList.size()+5];
    to=new int[(int)edgeList.size()+5];
    std::fill_n(info,n,0);
    for(size_t i=0;i<edgeList.size();++i)
    {
        to[i+1]=edgeList[i].second;
        next[i+1]=info[edgeList[i].first];
        info[edgeList[i].first]=i+1;
    }
    std::fill_n(instack,n,0);
    colorCnt=0;
    curr=0;
    for(int i=0;i<n;i++)
        if(!instack[i]) dfs(i);
    delete[] instack;
    delete[] dfn;
    delete[] low;
    delete[] info;
    delete[] next;
    delete[] to;
}

};

## 题库

|ID|TITLE|CODE(C/C++)|备注|
|:-:|:-:|:-:|:-:|
|[POJ2186](http://poj.org/problem?id=2186)|Popular Cows|查看代码||