poj 2553 The Bottom of a Graph 【强连通图中出度为0点】

短命女 2022-08-13 15:46 112阅读 0赞

题目：[poj 2553 The Bottom of a Graph ][poj 2553 The Bottom of a Graph]

题意：大概题意是给出一个有向图，求强连通缩点以后出度为0的点。

分析：入门题目，先强连通缩点，然后表示出度为0的，枚举输出即可。

#include <cstdio>
    #include <vector>
    #include <iostream>
    #include <stack>
    #include <cstring>
    using namespace std;
    const int N = 25000;
    vector<int> G[N];
    int pre[N],lowlink[N],sccno[N],dfs_clock,scc_cnt; //sccno【i】 i所在的scc图的编号
    //scc_cnt 联通块的数量
    stack<int> s;
    
    void dfs(int u)
    {
        pre[u] = lowlink[u] = ++dfs_clock;
        s.push(u);
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(!pre[v])
            {
                dfs(v);
                lowlink[u]=min(lowlink[u],lowlink[v]);
            }
            else if(!sccno[v])
            {
                lowlink[u]=min(lowlink[u],pre[v]);
            }
        }
        if(lowlink[u]==pre[u])
        {
            scc_cnt++;
            for(;;)
            {
                int x=s.top();
                s.pop();
                sccno[x]=scc_cnt;
                if(x==u)
                    break;
            }
        }
    }
    void find_scc(int n)
    {
        dfs_clock=scc_cnt=0;
        memset(sccno,0,sizeof(sccno));
        memset(pre,0,sizeof(pre));
        for(int i=0; i<n; i++)
            if(!pre[i]) dfs(i);
    }
    int in[N],out[N];
    int flag[N];
    vector<int> ans;
    void workout(int n) {
        memset(out,0,sizeof(out));
        memset(flag,0,sizeof(flag));
        for (int u = 0; u < n; u++) {
            for (int i = 0; i < G[u].size(); i++) {
                int v = G[u][i];
                //printf("%d %d %d %d\n",u+1,v+1,sccno[u],sccno[v]);
                if (sccno[u] != sccno[v]) {
                    out[sccno[u]] += 1;
                }
            }
        }
        for (int i = 1; i <= scc_cnt; i++) {
            if (out[i] == 0) flag[i] = 1;
        }
        for(int i=0;i<n;i++)
        {
            if(flag[sccno[i]])
                ans.push_back(i+1);
        }
        for(int i=0;i<ans.size();i++)
        {
            printf("%d%c",ans[i],i==(ans.size()-1)?'\n':' ');
        }
        ans.clear();
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,m,T;
        while(~scanf("%d",&n) && n)
        {
            scanf("%d",&m);
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                G[x-1].push_back(y-1);
            }
            find_scc(n);
            workout(n);
            for(int i=0;i<n;i++)
                G[i].clear();
        }
        return 0;
    }

[poj 2553 The Bottom of a Graph]: http://poj.org/problem?id=2553