随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

poj2762 Going from u to v or from v to u? 强连通分支

又贡献了一版的WA和TLE一道题,本来不是很难,但是由于初始化有问题,一直RE。
先说说这道题的思路吧,两次dfs进行缩点,缩点之后再深搜一次找出最长路径与缩点之后的顶点数相比,
相等则输出Yes,否则输出No。

#include<iostream>
using namespace std;

struct node{
    
int v;
    node 
*next;
}
;

node pp[
6005],qq[6005];
node 
*dd[1005],*rd[1005];
bool mark[1005];
bool map[1005][1005];
int cal[1005];
int ret[1005];
int n,m,ti;

void init()
{
    memset(mark,
false,sizeof(mark));
    memset(cal,
0,sizeof(cal));
    memset(dd,
0,sizeof(dd));
    memset(rd,
0,sizeof(rd));
    memset(ret,
0,sizeof(ret));
    memset(map,
false,sizeof(map));
}


void input()
{
    
int u,v,i;
    scanf(
"%d%d",&n,&m);
    
for(i=0;i<m;i++){
        scanf(
"%d%d",&u,&v);
        pp[i].v
=v;
        pp[i].next
=dd[u];
        dd[u]
=&pp[i];
        
        qq[i].v
=u;
        qq[i].next
=rd[v];
        rd[v]
=&qq[i];
    }

}
        

void dfs(int k)
{
    mark[k]
=true;
    node 
*p=dd[k];
    
while(p){
        
if(!mark[p->v])
            dfs(p
->v);
        p
=p->next;
    }

    cal[
++ti]=k;
}


void rdfs(int k){
    ret[k]
=ti;
    node 
*p=rd[k];
    
while(p){
        
if(!ret[p->v]) 
            rdfs(p
->v);
        
else if(ti!=ret[p->v]){
            map[ti][ret[p
->v]]=true;
        }

        p
=p->next;
    }

}


int dfsr(int k){
    
int ans=0;
    
for(int i=1;i<=ti;i++){
        
if(map[k][i]){
            
if(!cal[i])
                dfsr(i);
            ans
=max(ans,cal[i]);
        }

    }

    cal[k]
=ans+1;
    
return cal[k];
}


int main()
{
    
int t,i;
    scanf(
"%d",&t);
    
while(t--){
        init();
        input();
        ti
=0;
        
for(i=1;i<=n;i++)
            
if(!mark[i])
                dfs(i);
        
for(ti=0,i=n;i>0;i--){
            
if(!ret[cal[i]]){
                ti
++;
                rdfs(cal[i]);
            }

        }

        
int ans=0;
        memset(cal,
0,sizeof(cal));
        
for(i=1;i<=ti;i++){
            
if(!cal[i])
                dfsr(i);
            ans
=max(ans,cal[i]);
        }

        
if(ans==ti) printf("Yes\n");
        
else printf("No\n");
    }

    
return 0;
}

posted on 2010-04-17 11:41 acleast 阅读(274) 评论(0)  编辑 收藏 引用


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