The Fourth Dimension Space

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

POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点)

也许你能写出一段精致的文字,但你却未必能写出一段精辟的代码。
这是我最近研究连通性问题的一个体验,有的人的书写了好几页纸,可是最终能用的却只有1,2句话而已,我觉得在计算机的世界,没有什么比代码更能直接地表达出这个算法的本质了!所以我以后要多读代码,少看那些空洞的文字。
言归正传,来看题,这是我写的第一个强连通分量的题目,其实求强连通分量的步骤非常简单,正反两次使用dfs,就能得到联通分量的一切信息。做完题目我发现,其实求联通分量最大的作用倒在于,联通分量可以缩成一点,考虑为一个整体,这样可以简化构图,发掘出各个强连通分量外部之间的规律。
解题的方法就是:找出图中所有的强连通分量并将他们缩成一点,再用外部的边重新建图,统计出新图中出度为0的点,如果只有一个,那么说明这个强连通分量中的所有点就是题目要求的点。

题目中要特别注意:内存池中预开的点必须是边的三倍大小,因为构建正图,反图和新图都需要新建节点。(因为这个我wa了一次)
还有就是绝对不要使用vector,我用vector写了一个程序,跑了600+MS,用链表.....47MS......10倍以上的差距,汗 - -!

#include<iostream>
using namespace std;
#define DOTMAX 10001
#define EDGEMAX 50001
struct node
{
    
int t;
    node 
*next;
}
dotset[EDGEMAX*3];

int count=0;//每一个case后,count置为0
node *Newnode()
{
    node 
*p;
    p
=&dotset[count];
    count
++;
    
return p;
}


void Addnode(node hash[],int a,int b)
{
    node 
*p=&hash[a];
    node 
*q=Newnode();
    q
->t=b;
    q
->next=p->next;
    p
->next=q;
}


node hash[DOTMAX];
node nhash[DOTMAX];
node New[DOTMAX];

int gcc;
int order[DOTMAX];
int num;
int id[DOTMAX];
int visit[DOTMAX];
int gccnum[DOTMAX];

void init(node hash[],int n)
{
    count
=0;
    
int i;
    
for(i=1;i<=n;i++)
    
{

        hash[i].t
=-1;
        hash[i].next
=NULL;
    }

}


int n,m;
void dfs(int u)
{

    visit[u]
=1;
    node 
*p;
    
int v;
    
for(p=hash[u].next;p!=NULL;p=p->next)
    
{
        v
=p->t;
        
if(!visit[v])
        
{
            dfs(v);
        }

    }

    num
++;
    order[num]
=u;
}


void ndfs(int u)
{

    visit[u]
=1;
    id[u]
=gcc;
    node 
*p;
    
int v;
    
for(p=nhash[u].next;p!=NULL;p=p->next)
    
{

        v
=p->t;
        
if(!visit[v])
        
{
            ndfs(v);
        }

    }

}



int main()
{
    
int a,b,i;
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{

        init(hash,n);
        init(nhash,n);
        init(New,n);
        
for(i=1;i<=m;i++)
        
{

            scanf(
"%d%d",&a,&b);
            Addnode(hash,a,b);
            Addnode(nhash,b,a);
        }

        memset(visit,
0,sizeof(visit));
        num
=0;
        
for(i=1;i<=n;i++)
        
{
            
if(!visit[i])
                dfs(i);
        }

        memset(visit,
0,sizeof(visit));
        gcc
=0;
        
for(i=num;i>=1;i--)
        
{

            
if(!visit[order[i]])
            
{
                gcc
++;
                ndfs(order[i]);
            }

        }

        
for(i=1;i<=n;i++)
        
{
            node 
*p;
            
for(p=hash[i].next;p!=NULL;p=p->next)
            
{
                
if(id[i]!=id[p->t])
                
{

                    Addnode(New,id[i],id[p
->t]);
                }



            }

        }

        
int cnt=0;
        memset(gccnum,
0,sizeof(gccnum));
        
for(i=1;i<=n;i++)
        
{

            gccnum[id[i]]
++;
        }


        
int mark=0;
        
for(i=1;i<=gcc;i++)
        
{
            
if(New[i].next==NULL)
            
            
{
                cnt
++;
                mark
=i;
            }

        }


        
if(cnt==1)
        
{

            printf(
"%d\n",gccnum[mark]);
        }

        
else
            printf(
"%d\n",0);
    }

return 0;

}


posted on 2009-09-26 17:40 abilitytao 阅读(2168) 评论(6)  编辑 收藏 引用

评论

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2009-09-30 11:35 foxinhongyan

一点注释都没有,不是什么好代码  回复  更多评论   

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2009-09-30 13:55 溪流

@foxinhongyan

在追求性能的地方(如 ACM),通常不容易看到好代码:)  回复  更多评论   

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2009-09-30 18:06 abilitytao

@foxinhongyan
@溪流
在下不才 还请二位前辈多多指教  回复  更多评论   

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2009-10-10 17:57 Ocean.Tu

代码就应该像女生的裙子  回复  更多评论   

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2009-10-15 21:37 溪流

@Ocean.Tu

“像女生的裙子”是怎么样的?  回复  更多评论   

# re: POJ 2186 Popular Cows(图的连通性问题——有向图的强联通分量+缩点) 2010-03-24 13:33 Wy.Lee

@溪流
越短越好  回复  更多评论   


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