今天想看看关于桥的求法，搜到了这样一个题，由与网上缺少相关的资料，花了很多时间在找资料上，最后发现lrj的书上有这个问题的描述:
无向图的割点和桥（见lrj书）
算法基于以下原理：（1）如果根顶点的儿子数大于1，则根顶点是割点（2）如果一个点和这个点的子孙都不存在指向这个点祖先的后向边，则这个点为割点。实现时需要对每个结点记录一个low值，表示该结点的子孙能够到达的最小的深度，如果这个值小于或等于该点的深度，则该点为割点。如果
y是x的儿子并且y的low值大于x的深度，则边(x,y)为图的桥。
原来求割点和求割边是同一回事，难怪网上只有割点的资料，割边的几乎没有提及。具体的算法看lrj的书，这里说一下做题的心得。
主要是两个方面：
1。题目中给出的图是有重边的，如何判断重边？这个问题很重要 根据题意，没法确定重边中的那一条边会被烧掉，所以重边一定不是我们想要的结果，要从求出的桥里面剔除。我想了比较长的时间，开矩阵吧，10000*10000的矩阵虽然定位是O(1)的，但是这么大的矩阵肯定爆。
所以只能用邻接表。可邻接表如何判重，难道线性扫描一遍？每一次加边都要从表头扫到表尾，然后才能实现插入，最坏的情况是0+1+2+3+...+m-1=O(m^2)。（当然这有点极端，毕竟n只有10000级别，是边的十分之一）建立邻接表的复杂度就有点。。。另外 20个case。。。
但是事实上，这道题我就是这么做的，邻接表+内存池，线性扫描判重，用的时间大约是时限的五分之一。。。可以接受。。。
2。这个题中给出的是无向边，建邻接表的时候正反都要建，但是一但正向被搜索过，方向就定了，DFS的过程实际就是将一个无向图，转换成一个有根的有向的深度优先生成树的过程。所以，每考察一个节点就要记录下他的父亲节点，不能将父子边当成回边，这个要特别注意。然后就是
low[ p->t ]> dfsn[k]
重边的时候要特殊照顾，其余的就是标准的算法过程了。
另外要使用邻接表的时候，不要用vector,效率实在太低，指针+内存池才是王道！
//This is the source code for ZOJ 2588
//Coded By abilitytao
//2009年9月26日
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define DOTMAX 10001
#define EDGEMAX 100001
#define min(a,b) ( (a)<(b)?(a):(b) )
int cmp(const void *a,const void *b)
{
return (*(int*)a)-(*(int*)b);
}
struct node
{
int t;
int index;
int num;
node *next;
}dotset[EDGEMAX*2];
node hash[DOTMAX];
int record[EDGEMAX];
int count=0;
node *Newnode()
{
node *p;
p=&dotset[count];
count++;
return p;
}
void init(int n)
{
int i;
for(i=1;i<=n;i++)
{
hash[i].next=NULL;
hash[i].t=-1;
}
}
void inputcase(int n,int m)
{
int flag;
int i;
init(n);
int a,b;
node *p;
node *q;
for(i=1;i<=m;i++)
{
flag=0;
scanf("%d%d",&a,&b);
for(p=&hash[a];p->next!=NULL;p=p->next)
{
if(p->t==b&&p->num==1)
{
flag=1;
break;
}
else if(p->t==b&&p->num==0)
{
flag=1;
p->num+=1;
break;
}
}
if(flag==1)
continue;
while(p->next!=NULL)
{
p=p->next;
}
q=Newnode();
q->t=b;
q->index=i;
q->num=0;
q->next=NULL;
p->next=q;
/**///////////////////////////////////////////////////////////////////////////
p=&hash[b];
q=Newnode();
q->index=i;
q->t=a;
q->num=0;
q->next=p->next;
p->next=q;
}
}
int res=0;
void dfs( int father,int k,int s,int &cnt,node hash[],bool visit[],int dfsn[],int low[])
{
++cnt;
dfsn[k]= cnt, low[k]= cnt, visit[k]= true;
int num= 0;
node *p;
for( p=hash[k].next ;p!=NULL; p=p->next )
{
if(p->t==father)
continue;
if( !visit[ p->t ] )
{
num++;
dfs(k,p->t,s,cnt,hash,visit,dfsn,low );
low[k]= min( low[k], low[ p->t ] );
if( low[ p->t ]> dfsn[k] )
{
if(p->num==0)
{
res++;
record[res]=p->index;
}
}
}
else if(k!=p->t)
low[k]= min( low[k], dfsn[ p->t ] );
}
}
int FindKeyPoint(node hash[],int s,int n)
{
int cnt=0;
bool visit[DOTMAX]={false};
int low[DOTMAX]={0};
int dfsn[DOTMAX]={0};
dfs(-1,s,s,cnt,hash,visit,dfsn,low);
return res;
}
int main()
{
int testcase;
scanf("%d",&testcase);
int i,j;
int n,m;
int num;
for(i=1;i<=testcase;i++)
{
res=0;
count=0;
scanf("%d%d",&n,&m);
inputcase(n,m);
num=FindKeyPoint(hash,1,n);
qsort(record+1,num,sizeof(record[0]),cmp);
printf("%d\n",num);
j=1;
for(j=1;j<num;j++)
{
printf("%d ",record[j]);
}
if(num!=0)
printf("%d\n",record[j]);
if(i!=testcase)
printf("\n");
}
return 0;
}