注意缩点后新建的图的顶点数可能达到2*n-1 (二)

void addedge(int u,int v,int id,int * head){
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].id=id;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt].id=id;
edge[cnt].next=head[v];
head[v]=cnt++;
}

void init(){
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head2));
memset(dfn,0,sizeof(dfn));
memset(color,0,sizeof(color));
memset(cut,0,sizeof(cut));
depth=c=cnt=0;
for(int i=0;i memset(edge_belong,0,sizeof(edge_belong));
}

void tarjan(int u,int fa){
int i,j;
dfn[u]=low[u]=++depth;
for(i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
if(dfn[v]==0){
ss.push(i);
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
cut[u]++;
c++;
do{
j=ss.top();
//printf("%d-%d ",edge[j].u,edge[j].v);
ss.pop();
edge_belong[edge[j].id]=c;
if(color[edge[j].u]!=c){
color[edge[j].u]=c;
dpt[c].push_back(edge[j].u);
node_bcc[edge[j].u].push_back(c);
}
if(color[edge[j].v]!=c){
color[edge[j].v]=c;
dpt[c].push_back(edge[j].v);
node_bcc[edge[j].v].push_back(c);
}
}while(j!=i);
//puts("");
}
}
else{
low[u]=min(low[u],dfn[v]);
if(dfn[u]>dfn[v]) ss.push(i); //这句话必须这么写！！否则打印点双联通内部的边会出错
}
}
}

int main(){
int n,m,i,j,u,v;
scanf("%d %d",&n,&m);
init();
for(i=1;i<=m;i++){
scanf("%d %d",&u,&v);
addedge(u,v,i,head);
}
for(i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
cut[i]--; //对于树根要减1
}
}
/*printf("%d\n",c);

for(i=1;i<=c;i++){
for(j=0;j puts("");
}*/

b=c;
for(i=1;i<=n;i++) if(cut[i]) color[i]=++c;

for(i=1;i<=n;i++)
for(j=0;j u=dpt[i][j];
if(cut[u]){
addedge(color[u],i,0,head2);
}
}

/*for(i=1;i<=m;i++) printf("%d:%d\n",i,edge_belong[i]);
for(i=1;i<=n;i++){
for(j=0;j puts("");
}*/
return 0;
}