poj 2186 Popular Cows



用adj作为邻接表,存正向的边,把边反向存在adj_op里。

第一次dfs1确定一颗深度优先搜索树,用finish记录访问顺序,然后从finish后面往前进行dfs2,每一次dfs2可以确定一个强连通分量。

证明参考算法导论

#include<iostream>
#include<vector>
using namespace std;
const int MAX=10005;
vector<int>adj[MAX], adj_op[MAX];
bool visit[MAX]={0},out[MAX];
int sblg[MAX],n,m;
vector<int> finish;
void dfs1(int i)
{
         if(visit[i])return ;
         visit[i]=true;
         for(int k=0; k<adj[i].size(); k++)
                 if(!visit[adj[i][k]])dfs1(adj[i][k]);
         finish.push_back(i);                 
}

void dfs2(int i, int c)
{
     if(visit[i])return ;
     visit[i]=true;  
     sblg[i]=c;
     for(int k=0; k<adj_op[i].size(); k++)
             if(!visit[adj_op[i][k]])dfs2(adj_op[i][k],c);
}

int main()
{
    while(cin>>n>>m)
    {
        memset(visit,0,sizeof visit); memset(out,0,sizeof out); memset(sblg,0,sizeof sblg);
        for(int i=1; i<=n; i++){ adj[i].clear(); adj_op[i].clear(); }
        int u,v;
        for(int i=1; i<=m; i++)
               {
                     cin>>u>>v;
                     adj[u].push_back(v);
                     adj_op[v].push_back(u);
               }    
        for(int i=1; i<=n; i++)
                if(!visit[i])dfs1(i);
        memset(visit,0,sizeof visit);
        int cnt=0;
        
        
        for(int i=finish.size()-1; i>=0; i--)
        {
                if(!visit[finish[i]])
                {
                    cnt++;
                    dfs2(finish[i],cnt);
                }
        }
       
        for(int i=1; i<=n; i++)
        {
                for(int j=0; j<adj[i].size(); j++)
                {
                        if(sblg[i]!=sblg[adj[i][j]])out[sblg[i]]=true;
                }
        }
        int count=0,index=0,num=0;
        for(int i=1; i<=cnt; i++)
                if(out[i]==0){ count++;index=i; }
        //for(int i=1; i<=n; i++)                
          //      cout<<sblg[i]<<endl;
        if(count==1)
        {
                   for(int i=1; i<=n; i++)
                           if(sblg[i]==index)num++;
                   cout<<num<<endl;
        }
        else cout<<0<<endl;
            
    }
    
    return 0;
}

posted on 2010-08-17 20:07 田兵 阅读(125) 评论(0)  编辑 收藏 引用 所属分类: POJ


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


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜