首页 > 代码库 > ZOJ 2588
ZOJ 2588
求一个无向图的桥（可能存在重边），输出割边的数目，并按顺序输出割边的序号(输入的顺序）。
由于内存的限制 , 无法使用邻接矩阵 , 只能用邻接表了 .
第一次用了邻接表，超内存了；
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <string.h> 5 using namespace std; 6 const int N=10002; 7 const int M=1000002; 8 struct edge{ 9 int v,next,id,two=0;10 }e[M];11 int k,first[M],id,count1; //first[i]是以点i为起点的链表头部12 int dfn[N],low[N],bri[M],mun;13 void init(){14 k=1;15 count1=0;16 mun=0;17 id=0;18 memset(first,0,sizeof(first));19 memset(low,0,sizeof(low));20 memset(dfn,0,sizeof(dfn));21 memset(bri,0,sizeof(bri));22 }23 void addedge(int a,int b){ //向图中加边的算法，注意加上的是有向边//b为a的后续节点既是a---->b24 int i;25 for(i=first[a];i;i=e[i].next){26 if(e[i].v==b)break;27 }28 if(i){ //方法稍作修改，用来标注重边29 e[i].two=1;30 return ;31 }32 e[k].v=b;33 e[k].next=first[a];34 e[k].id=id;35 e[k].two=0;36 first[a]=k++;37 }38 void dfs(int u,int far){ //dfn,Tarjan算法 39 dfn[u]=low[u]=++count1;40 for(int i=first[u];i;i=e[i].next){41 int v=e[i].v;42 if(!dfn[v]){43 dfs(v,u);44 low[u]=min(low[u],low[v]);45 if(low[v]>dfn[u]&&!e[i].two){46 bri[mun++]=e[i].id;47 }48 49 }50 else if(v!=far)low[u]=min(low[u],dfn[v]);51 }52 }53 void print(){54 printf("%d\n",mun);55 if(mun>0){56 sort(bri,bri+mun);57 printf("%d",bri[0]);58 for(int i=1;i<mun;i++)59 printf(" %d",bri[i]);60 printf("\n");61 }62 }63 int main(){64 int t,n,m,a,b;65 scanf("%d",&t);66 while(t--){67 init();68 scanf("%d%d",&n,&m);69 while(m--){70 scanf("%d%d",&a,&b);71 id++;72 addedge(a,b);73 addedge(b,a);74 }75 dfs(1,0);76 print();77 if(t)printf("\n");78 }79 return 0;80 }
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=10002;
const int M=1000002;
struct edge{
int v,next,id,two=0;
}e[M];
int k,first[M],id,count1;
int dfn[N],low[N],bri[M],mun;
void init(){
k=1;
count1=0;
mun=0;
id=0;
memset(first,0,sizeof(first));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(bri,0,sizeof(bri));
}
void addedge(int a,int b){
int i;
for(i=first[a];i;i=e[i].next){
if(e[i].v==b)break;
}
if(i){
e[i].two=1;
return ;
}
e[k].v=b;
e[k].next=first[a];
e[k].id=id;
e[k].two=0;
first[a]=k++;
}
void dfs(int u,int far){
dfn[u]=low[u]=++count1;
for(int i=first[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]&&!e[i].two){
bri[mun++]=e[i].id;
}
}
else if(v!=far)low[u]=min(low[u],dfn[v]);
}
}
void print(){
printf("%d\n",mun);
if(mun>0){
sort(bri,bri+mun);
printf("%d",bri[0]);
for(int i=1;i<mun;i++)
printf(" %d",bri[i]);
printf("\n");
}
}
int main(){
int t,n,m,a,b;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&a,&b);
id++;
addedge(a,b);
addedge(b,a);
}
dfs(1,0);
print();
if(t)printf("\n");
}
return 0;
}