Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3180---The Cow Prom 强连通分量

Posted on 2010-07-24 22:29 Uriel 阅读(471) 评论(0)  编辑 收藏 引用 所属分类: POJ图论
        题意依旧纠结,建图依旧纠结。。
        求含结点数>=2的连通分量数。。
        PS:难得有图论题搜不到DY大牛的解题报告~

        用这题来试了各种求强连通分量的模板(今天两题都用来试模板,然后狂刷。。)  
        结果如下:      
                        Kosaraju:G++(加读入输出优化):172Ms
                            Tarjan:C++(不加读入输出优化):204Ms
                                          G++(不加读入输出优化):250Ms
                                          G++(加读入输出优化):94Ms
       Tarjan+Disjoint Sets:G++(加读入输出优化):16Ms 暂时Rank 1

求连通分量部分基本是贴代码的,Tarjan的代码感谢光光提供模板~
代码比较挫。。可以无视。。

Version:Kosaraju
//Problem: 3180  User: Uriel 
//Memory: 2120K  Time: 172MS 
//Language: G++  Result: Accepted 
//Version: [Kosaraju]
//2010.07.24
#include<vector>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
using namespace std;
#define MAXN 10010

int e,v; //边数,顶点数
int flag; //连通分量数
int link[MAXN]; //标色数组
int size[MAXN]; //每个连通分量包含的顶点数
int order[MAXN]; //DFS1序列
int num,res;
bool vis[MAXN];
vector
<int>adja[MAXN];//正向
vector<int>adjb[MAXN];//逆向

void DFS1(int x){
    vis[x]
=true;
    
for(int i=0;i<adja[x].size();i++)
        
if(!vis[adja[x][i]])DFS1(adja[x][i]);
    order[
++num]=x;
}

void DFS2(int x){
    vis[x]
=true;
    link[x]
=flag;
    size[flag]
++;
    
for(int i=0;i<adjb[x].size();i++)
        
if(!vis[adjb[x][i]])DFS2(adjb[x][i]);
}

void Kosaraju(){
    
int i;
    memset(vis,
0,sizeof(vis));
    num
=0;
    
for(i=1;i<=v;i++)
        
if(!vis[i])DFS1(i);
    memset(vis,
0,sizeof(vis));
    memset(size,
0,sizeof(size));
    flag
=0;
    
for(i=num;i>=1;i--){
        
if(!vis[order[i]]){
            flag
++;
            DFS2(order[i]);
        }

    }

}


int in(){
    
char ch;
    
int a=0;
    
while((ch=getchar())==' ' || ch=='\n');
    a
*=10;
    a
+=ch-'0';
    
while((ch=getchar())!=' ' && ch!='\n'){
        a
*=10;a+=ch-'0';
    }

    
return a;
}


void out(int a){
    
if(a>=10)out(a/10);
    putchar(a
%10+'0');
}


int main(){
    
int x,y,i;
    v
=in();e=in();
    
for(i=0;i<e;i++){
        x
=in();y=in();
        adja[x].push_back(y);
        adjb[y].push_back(x);
    }

    Kosaraju();
    res
=0;
    
for(i=1;i<=flag;i++){
        
if(size[i]>=2)res++;
    }

    
out(res);
    putchar(
'\n');
    
return 0;
}


Version:Tarjan
//Problem: 3180  User: Uriel 
//Memory: 1596K  Time: 94MS 
//Language: G++  Result: Accepted
////Version: [Tarjan]
////2010.07.24

#include<vector>
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
using namespace std;

#define N 10010

int n,m,res;
int dfn[N],low[N],instack[N];
int belong[N],stap[N],cnt[N];
int stop,bcnt,dindex;

vector
<int>vec[N];

void Tarjan(int i){
    
int j;
    dfn[i]
=low[i]=++dindex;
    instack[i]
=true;
    stap[
++stop]=i;
    vector
<int>::iterator it;
    
for(it=vec[i].begin();it!=vec[i].end();it++){
        j
=*it;
        
if(!dfn[j]){
            Tarjan(j);
            
if(low[j]<low[i])low[i]=low[j];
        }

        
else if(instack[j] && dfn[j]<low[i])low[i]=dfn[j];
    }

    
if(dfn[i]==low[i]){
        bcnt
++;
        
do{
            belong[j
=stap[stop--]]=bcnt;
            cnt[bcnt]
++;
            instack[j]
=false;

        }
while(j!=i);
    }

}


void Sov(){
    
int i;
    stop
=bcnt=dindex=0;
    memset(dfn,
0,sizeof(dfn));
    memset(cnt,
0,sizeof(cnt));
    
for(i=1;i<=n;i++)
        
if(!dfn[i])Tarjan(i);
}


int in(){
    
char ch;
    
int a=0;
    
while((ch=getchar())==' ' || ch=='\n');
    a
*=10;
    a
+=ch-'0';
    
while((ch=getchar())!=' ' && ch!='\n'){
        a
*=10;a+=ch-'0';
    }

    
return a;
}


void out(int a){
    
if(a>=10)out(a/10);
    putchar(a
%10+'0');
}


int main(){
    
int a,b,i;
    n
=in();m=in();
    
for(i=0;i<m;i++){
        a
=in();b=in();
        vec[a].push_back(b);
    }

    Sov();
    res
=0;
    
for(i=0;i<=bcnt;i++)
        
if(cnt[i]>=2)res++;
    
out(res);
    putchar(
'\n');
    
return 0;
}

Version:Tarjan+Disjoint Sets
//Problem: 3180  User: Uriel 
//Memory: 1072K  Time: 32MS 
//Language: G++  Result: Accepted 
//Version: [Tarjan+Tarjan+Disjoint Sets]
//2010.07.24
#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

struct node{
    
int y,next;
}
;

int e;
int n; //
int m; //
int res;
int head[10010],co[10010],father[10010],link[10010],order[10010];
node p[
50010];

int in(){
    
char ch;
    
int a=0;
    
while((ch=getchar())==' ' || ch=='\n');
    a
*=10;
    a
+=ch-'0';
    
while((ch=getchar())!=' ' && ch!='\n'){
        a
*=10;a+=ch-'0';
    }

    
return a;
}


void out(int a){
    
if(a>=10)out(a/10);
    putchar(a
%10+'0');
}


void addedge(int x,int y){
    p[e].y
=y;p[e].next=head[x];
    head[x]
=e++;
}


void init(){
    
int num,x,y;
    e
=0;
    memset(head,
-1,sizeof(head));
    memset(link,
0,sizeof(link));
    memset(order,
0,sizeof(order));
    n
=in();
    m
=in();
    
for(int i=1;i<=m;i++){
        x
=in();
        y
=in();
        addedge(x,y);
    }

}


int Find(int x){
    
if(father[x]==x)return x;
    father[x]
=Find(father[x]);
    
return father[x];
}


void DFS(int x){
    
for(int i=head[x];i!=-1;i=p[i].next){
        
if(order[p[i].y]==0){
            order[p[i].y]
=order[x]+1;
            DFS(p[i].y);
            
if(order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
        }

        
else if(co[Find(p[i].y)]==0 && order[Find(p[i].y)]<order[Find(x)])father[x]=father[p[i].y];
    }

    co[x]
=1;
}


void Tarjan(){
    
for(int i=1;i<=n;i++)father[i]=i;
    
for(int i=1;i<=n;i++){
        
if(order[i]==0){
            order[i]
=1;
            DFS(i);
        }

    }

    
for(int i=1;i<=n;i++)Find(i);
}


int main()
{
    init();
    Tarjan();
    
for(int i=1;i<=n;i++){
        
for(int j=head[i];j!=-1;j=p[j].next){
            link[father[i]]
++;
        }

    }

    res
=0;
    
for(int i=1;i<=n;i++)
        
if(link[i]>=2)res++;
    printf(
"%d\n",res);
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理