当前位置 : 主页 > 编程语言 > java >

Tarjan

来源:互联网 收集:自由互联 发布时间:2022-09-02
//记得每次清边 vectorintEdge[maxm]; stackintS; int Dfn[maxn],Low[maxn],sccno[maxn],tclock,sccnt;//sccno代表某个点所在的强连通分量编号 void tarjan(int u){ Dfn[u] = Low[u] = ++tclock; S.push(u); for(int i = 0;i Edge[u].si


//记得每次清边
vector<int>Edge[maxm];
stack<int>S;
int Dfn[maxn],Low[maxn],sccno[maxn],tclock,sccnt;//sccno代表某个点所在的强连通分量编号

void tarjan(int u){
Dfn[u] = Low[u] = ++tclock;
S.push(u);

for(int i = 0;i < Edge[u].size();i++){
int v = Edge[u][i];
if(!Dfn[v]){
tarjan(v);
Low[u] = min(Low[u],Low[v]);
}
else if(!sccno[v]){
Low[u] = min(Low[u],Dfn[v]);
}
}

if(Low[u] == Dfn[u]){
sccnt ++;
int v = -1;
while(v != u){
v = S.top();
S.pop();
sccno[v] = sccnt;
}
}
}

void findscc(int n){
tclock = sccnt = 0;
//各种数组初始化
memset(Dfn,0,sizeof(Dfn));
memset(Low,0,sizeof(Low));
memset(sccno,0,sizeof(sccno));
for(int i = 1;i <= n;i++)
if(!Dfn[i]) tarjan(i);
}


上一篇:hdoj 5948 Thickest Burger
下一篇:没有了
网友评论