使用Tarjan进行缩点无向图

int From[maxn],Laxt[maxn],To[maxn<<2],Next[maxn<<2],cnt;

int low[maxn],dfn[maxn],times,q[maxn],head,scc_cnt,scc[maxn];

vectorG[maxn];

int dis[maxn],S,T,ans;

void add(int u,int v)

{

Next[++cnt]=Laxt[u]; From[cnt]=u;

Laxt[u]=cnt; To[cnt]=v;

}

void tarjan(int u,int fa)

{

dfn[u]=low[u]=++times;

q[++head]=u;

for(int i=Laxt[u];i;i=Next[i]){

if(To[i]fa) continue;

if(!dfn[To[i]]) {

tarjan(To[i],u);

low[u]=min(low[u],low[To[i]]);

}

else low[u]=min(low[u],dfn[To[i]]);

}

if(low[u]dfn[u]){

scc_cnt++;

while(true){

int x=q[head--];

scc[x]=scc_cnt;

if(x==u) break;

}

}

}

void init()

{

memset(Laxt, 0, sizeof(Laxt));

cnt = 0;

}

int main()

{

init();

int N,M,u,v,i,j;

scanf("%d%d",&N,&M);

for(i=1;i<=M;i++){

scanf("%d%d",&u,&v);

add(u,v); add(v,u);

}

tarjan(1,0);

for(i=1;i<=N;i++){

for(j=Laxt[i];j;j=Next[j]){

if(scc[i]!=scc[To[j]])

G[scc[i]].push_back(scc[To[j]]);

}

}

return 0;

}

巴特西

使用Tarjan进行缩点无向图

最新文章

热门文章