今天想看看關(guān)于橋的求法，搜到了這樣一個題，由與網(wǎng)上缺少相關(guān)的資料，花了很多時間在找資料上，最后發(fā)現(xiàn)lrj的書上有這個問題的描述:
無向圖的割點(diǎn)和橋（見lrj書）
算法基于以下原理：（1）如果根頂點(diǎn)的兒子數(shù)大于1，則根頂點(diǎn)是割點(diǎn)（2）如果一個點(diǎn)和這個點(diǎn)的子孫都不存在指向這個點(diǎn)祖先的后向邊，則這個點(diǎn)為割點(diǎn)。實(shí)現(xiàn)時需要對每個結(jié)點(diǎn)記錄一個low值，表示該結(jié)點(diǎn)的子孫能夠到達(dá)的最小的深度，如果這個值小于或等于該點(diǎn)的深度，則該點(diǎn)為割點(diǎn)。如果
y是x的兒子并且y的low值大于x的深度，則邊(x,y)為圖的橋。
原來求割點(diǎn)和求割邊是同一回事，難怪網(wǎng)上只有割點(diǎn)的資料，割邊的幾乎沒有提及。具體的算法看lrj的書，這里說一下做題的心得。
主要是兩個方面：
1。題目中給出的圖是有重邊的，如何判斷重邊？這個問題很重要 根據(jù)題意，沒法確定重邊中的那一條邊會被燒掉，所以重邊一定不是我們想要的結(jié)果，要從求出的橋里面剔除。我想了比較長的時間，開矩陣吧，10000*10000的矩陣雖然定位是O(1)的，但是這么大的矩陣肯定爆。
所以只能用鄰接表。可鄰接表如何判重，難道線性掃描一遍？每一次加邊都要從表頭掃到表尾，然后才能實(shí)現(xiàn)插入，最壞的情況是0+1+2+3+...+m-1=O(m^2)。（當(dāng)然這有點(diǎn)極端，畢竟n只有10000級別，是邊的十分之一）建立鄰接表的復(fù)雜度就有點(diǎn)。。。另外 20個case。。。
但是事實(shí)上，這道題我就是這么做的，鄰接表+內(nèi)存池，線性掃描判重，用的時間大約是時限的五分之一。。。可以接受。。。
2。這個題中給出的是無向邊，建鄰接表的時候正反都要建，但是一但正向被搜索過，方向就定了，DFS的過程實(shí)際就是將一個無向圖，轉(zhuǎn)換成一個有根的有向的深度優(yōu)先生成樹的過程。所以，每考察一個節(jié)點(diǎn)就要記錄下他的父親節(jié)點(diǎn)，不能將父子邊當(dāng)成回邊，這個要特別注意。然后就是
low[ p->t ]> dfsn[k]
重邊的時候要特殊照顧，其余的就是標(biāo)準(zhǔn)的算法過程了。
另外要使用鄰接表的時候，不要用vector,效率實(shí)在太低，指針+內(nèi)存池才是王道！
//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;
}