模板
[cpp]
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define N 2000 //注意縮點後新建的圖的頂點數可能達到2*n-1
#define M 600000 //縮點新建的圖一定是樹
using namespace std;
struct Edge{
int u,v,id,next;
}edge[M*2];
int head[N],head2[N],cnt;
int dfn[N],low[N],color[N],depth,c,b; //color數組指示每個割點或者點雙連通分支的在新圖的標號，割點標號均>=c
int cut[N]; //cut不為0表示是割點，分成cut+1塊
stack<int>ss;
vector<int>dpt[N]; //每個點連通分支所包含的節點
vector<int>node_bcc[N]; //每個節點所屬的點連通分支
int edge_belong[N]; //每條邊所屬的點連通分支
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<N;i++) dpt[i].clear(),node_bcc[i].clear();
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<dpt[i].size();j++) printf("%d ",dpt[i][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<dpt[i].size();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<node_bcc[i].size();j++) printf("%d ",node_bcc[i][j]);
puts("");
}*/
return 0;
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define N 2000 //注意縮點後新建的圖的頂點數可能達到2*n-1
#define M 600000 //縮點新建的圖一定是樹
using namespace std;
struct Edge{
int u,v,id,next;
}edge[M*2];
int head[N],head2[N],cnt;
int dfn[N],low[N],color[N],depth,c,b; //color數組指示每個割點或者點雙連通分支的在新圖的標號，割點標號均>=c
int cut[N]; //cut不為0表示是割點，分成cut+1塊
stack<int>ss;
vector<int>dpt[N]; //每個點連通分支所包含的節點
vector<int>node_bcc[N]; //每個節點所屬的點連通分支
int edge_belong[N]; //每條邊所屬的點連通分支
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<N;i++) dpt[i].clear(),node_bcc[i].clear();
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<dpt[i].size();j++) printf("%d ",dpt[i][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<dpt[i].size();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<node_bcc[i].size();j++) printf("%d ",node_bcc[i][j]);
puts("");
}*/
return 0;
}
