The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ZOJ 2588-Burning Bridges(图的连通性问题——求割边)

今天想看看关于桥的求法,搜到了这样一个题,由与网上缺少相关的资料,花了很多时间在找资料上,最后发现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;
}

posted on 2009-09-26 01:35 abilitytao 阅读(1402) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理