#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 using namespace std; #define N 1010 #define M 20010 struct node { int v;//下个顶点 node *next;//下个边结点 }; int n,m,r[N],d[N];//d表示缩点后各顶点的度数 node mem[M];int memp;//存储边结点 node *e[N]; int necc;//原图中边双连通分量的个数 int belong[N]; int low[N],dfn[N]; int vis[N]; int brig[M][2],nbrig; void addedge(int i,int j) { node *p=&mem[memp++]; p->v=j; p->next=e[i]; e[i]=p; } int root(int a) { if(a!=r[a]) r[a]=root(r[a]); return r[a]; } void merge(int a,int b) { int ra=root(a); int rb=root(b); if(ra!=rb) r[ra]=rb; } void dfs(int i,int father,int dth) { int j,tofa=0; node *p; vis[i]=1; low[i]=dfn[i]=dth; for(p=e[i];p!=NULL;p=p->next) { j=p->v; if(vis[j]&&(j!=father||tofa)) low[i]=min(low[i],dfn[j]); if(!vis[j]) { dfs(j,i,dth+1); low[i]=min(low[i],low[j]); if(low[j]<=dfn[i]) merge(i,j);//i,j在同一个双联通分量 if(low[j]>dfn[i]) //边i,j是桥 { brig[nbrig][0]=i; brig[nbrig++][1]=j; } } if(j==father) tofa=1; } vis[i]=2; } int doubleconne() { int i,k,ncon=nbrig=0; dfs(0,-1,1); for(i=0;i