现在的位置: 首页 > 综合 > 正文

poj 2553 The Bottom of a Graph(强连通分量)

2017年07月15日 ⁄ 综合 ⁄ 共 1475字 ⁄ 字号 评论关闭

题意:求解点v可达的点都能到达v的点的集合

只需要求出出度为0的强连通分量输出即可。属于简单模板题~~~

#include <iostream>
#include <vector>
#include <stack>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=5005;

int vN,e;

vector <int >grap[N];
stack<int> s;
int low[N];
int num[N];
int visited[N];
int instack[N];
int index;
int cnt_scc;
int belong[N];

int outdeg[N];
vector<int >ans;

void init()
{
    for(int i=0;i<=vN;i++)grap[i].clear();
    ans.clear();
    while(!s.empty())s.pop();
    memset(instack,0,(vN+2)*sizeof(int));
    memset(visited,0,(vN+2)*sizeof(int));
    memset(low,-1,(vN+2)*sizeof(int));
    memset(num,-1,(vN+2)*sizeof(int));
    memset(belong,-1,(vN+2)*sizeof(int));
    index=0;
    cnt_scc=0;

    memset(outdeg,0,(vN+2)*sizeof(int));
}

void tarjan(int v)
{
    low[v]=num[v]=++index;
    s.push(v);
    instack[v]=1;
    visited[v]=1;
    for(int i=0;i<grap[v].size();i++)
    {
        int w=grap[v][i];
        if(!visited[w])
        {
            tarjan(w);
            low[v]=min(low[v],low[w]);
        }
        else if(instack[w])
        {
            low[v]=min(low[v],low[w]);
        }
    }
    int u;
    if(low[v]==num[v])
    {
        ++cnt_scc;
        do
        {
            u=s.top();
            belong[u]=cnt_scc;
            s.pop();
            instack[u]=0;
        }while(u!=v);
    }
}
int main()
{
    while(cin>>vN&&vN!=0)
    {
        cin>>e;
        int i,j;
        init();
        for(i=0;i<e;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            grap[u].push_back(v);
        }
        for(i=1;i<=vN;i++)
        {
            if(!visited[i])tarjan(i);
        }
        for(i=1;i<=vN;i++)
        {
            for(j=0;j<grap[i].size();j++)
            {
                int k=grap[i][j];
                if(belong[i]!=belong[k])outdeg[belong[i]]++;
            }
        }
        for(i=1;i<=cnt_scc;i++)
        {
            if(outdeg[i]==0)
            {
                for(j=1;j<=vN;j++)
                {
                    if(belong[j]==i)ans.push_back(j);
                }
            }
        }
        sort(ans.begin(),ans.end());
        if(ans.size()==0)cout<<endl;
        else
        {
            for(i=0;i<ans.size();i++)cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

抱歉!评论已关闭.