HIHO #1190 : 连通性·四（点的双联通分量）

本文主要是介绍HIHO #1190 : 连通性·四（点的双联通分量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

点的双联通分量，不注意写出了一个bug，找了2个多小时= =，我的边存的是0开始的，然后ans数组一开始也是0，然后就是if的地方。。。。。

还是tarjan的算法，结合提示，这里需要存边，然后栈里面保存的是边，而不是点，这里我用边在边集es中的编号，作为边的标志

#include<bits/stdc++.h>
using namespace std;
#define cl(a,b) memset(a,b,sizeof(a))
#define fastIO ios::sync_with_stdio(false);cin.tie(0);
#define LL long long
#define pb push_back
#define gcd __gcd#define For(i,j,k) for(int i=(j);i<k;i++)
#define lowbit(i) (i&(-i))
#define _(x) printf("%d\n",x)const int maxn = 2e5+2000;
const int inf  = 1 << 28;int n,m;struct Edge{int from,to;
};vector<Edge> es;
vector<int> G[maxn];void addEdge(int from,int to){es.pb((Edge){from,to});int m = es.size()-1;G[from].pb(m);G[to].pb(m);
}int dfn[maxn],low[maxn],counter;
int stk[maxn],top,cnt;int belong[maxn];
int ans[maxn];void dfs(int u,int fa){dfn[u]=low[u]= ++counter;for(int i=0;i<G[u].size();i++){int num = G[u][i];int v = es[num].to==u?es[num].from:es[num].to;if(fa==v)continue;if(!dfn[v]){stk[top++] = num;dfs(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){++cnt;int x=0;do{x = stk[--top];belong[x] = cnt;//if(ans[cnt]==0)ans[cnt]=x;一开始这样写，导致了无限WA，因为我的边是从0开始的= =，切记！！ans[cnt]=min(ans[cnt],x);}while(x!=num);}}else if(dfn[v]<dfn[u]){low[u]=min(low[u],dfn[v]);stk[top++] = num;}}
}int main(){fastIO;cl(ans,127);//初始一个大的数字cin>>n>>m;for(int i=0;i<m;i++){int x,y;cin>>x>>y;addEdge(x,y);}dfs(1,1);cout<<cnt<<endl;for(int i=0;i<m;i++){//printf("%d-->%d , belong ->%d\n",es[i].from,es[i].to,belong[i]);if(i==0)cout<<ans[belong[i]]+1;else cout<<' '<<ans[belong[i]]+1;}cout<<endl;return 0;
}