poj 2553 The Bottom of a Graph

Accepted 1004K 297MS C++ 1585B

求出度为0的强连通分量,可能有多个,按节点序号从小到大输出就行了。

还是用两次DFS 加 名字不好记 加 还不知道怎么发音的的那个算法,第一次原图DFS确定访问顺序,第二次对翻转过边的方向得到的新图DFS

确定强连通分量。

还不太熟,写了一些时间。

#include<iostream>
#include
<vector>
using namespace std;
vector
<int> adj[5001];
vector
<int> adj_op[5001];
bool visit[5001];
int father[5001],outagree[5001];
vector
<int> finish;
int n,m;
void dfs1(int v)
{
    visit[v]
=true;
     
for(int i=0; i<adj[v].size(); i++)
         
if(!visit[adj[v][i]])
             dfs1(adj[v][i]);
    finish.push_back(v);
}

void dfs2(int v, int fa)
{
    visit[v]
=true;
    
for(int i=0; i<adj_op[v].size(); i++)
        
if(!visit[adj_op[v][i]])
        {
             father[adj_op[v][i]]
=fa;
             dfs2(adj_op[v][i],fa);
        }

}
int main()
{
    
while(cin>>n)
    {
        
if(n==0)break;
        cin
>>m;
        
int i,j,s,t;
        
for(i=1; i<=n; i++)
        {
            adj[i].clear();
            adj_op[i].clear();
        }

        
for(i=1; i<=m; i++)
        {
            cin
>>s>>t;
            adj[s].push_back(t);
            adj_op[t].push_back(s);
        }
        
        finish.clear();
        memset(visit, 
0sizeof visit);
        
for(i=1; i<=n; i++)
            
if(!visit[i])
                dfs1(i);

        memset(visit, 
0sizeof visit);
        memset(father,
0,sizeof father);
        
int cnt=0;
        
for(i=finish.size()-1; i>=0; i--)
            
if(!visit[finish[i]])
            {
                cnt
++;
                father[finish[i]]
=cnt;
                dfs2(finish[i],cnt);
            }
          
         
//for(i=1; i<=n; i++)
        
//     cout<<i<<' '<<father[i]<<endl;
         memset(outagree,0,sizeof outagree);
        
         
for(i=1; i<=n; i++)
             
for(j=0; j<adj[i].size(); j++)
             {
                 
if(father[i]!=father[ adj[i][j] ])
                     outagree[ father[i] ]
++;
             }
        
             
int tt=0;
             
for(i=1; i<=n; i++)
                 
if(outagree[father[i]]==0)
                 {
                     
if(tt!=0)cout<<' ';
                     cout
<<i;
                     tt
++;
                 }
             cout
<<endl;
    }

    
return 0;
}

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


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


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

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜