【poj2553】The Bottom of a Graph(强连通分量缩点)

时间：2024-05-16 21:07:02

题目链接：http://poj.org/problem?id=2553

【题意】

给n个点m条边构成一幅图，求出所有的sink点并按顺序输出。sink点是指该点能到达的点反过来又能回到该点。

【思路】

不难想象sink点一定是在强连通分量中，而且强连通分量缩点后出度为0，就可以说明该强连通分量内所有的点都是sink点。

之前wa了一发是因为写成了out[i]，注意是从缩点构成的dag中找出度为0的点，而不是从原来的图中找。

【ac代码】

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <stack>

#include <vector>

#include <cstring>

using namespace std;

const int N = ;

int low[N], vis[N], dfn[N], col[N], out[N], ans[N];

vector<int>V[N];

stack<int>s;

int n, cnt, num;

void dfs(int u)

{

    s.push(u);

    vis[u] = ;

    dfn[u] = low[u] = ++cnt;

    for (int i = ; i < V[u].size(); i++)

    {

        int v = V[u][i];

        if (!dfn[v])

        {

            dfs(v);

            low[u] = min(low[u], low[v]);

        }

        else if (vis[v])

            low[u] = min(low[u], dfn[v]);

    }

    if (low[u] == dfn[u])

    {

        int t;

        num++;

        do

        {

            t = s.top();

            s.pop();

            col[t] = num;

            vis[t] = ;

        }

        while (t != u);

    }

}

void tarjan()

{

    int i;

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    memset(vis, , sizeof(vis));

    memset(col, , sizeof(col));

    while (!s.empty()) s.pop();

    cnt = num = ;

    for (i = ; i <= n; i++)

        if (!dfn[i]) dfs(i);

}

int main()

{

    int m, i, j;

    while(scanf("%d", &n), n)

    {

        scanf("%d", &m);

        for(i = ; i <= n; i++) V[i].clear();

        int a, b;

        while(m--)

        {

            scanf("%d%d", &a, &b);

            V[a].push_back(b);

        }

        tarjan();

        memset(out, , sizeof out);

        for(i = ; i <= n; i++)

            for(j = ; j < V[i].size(); j++)

            {

                int v = V[i][j];

                if(col[i] != col[v]) out[col[i]]++;//该颜色出度+1

            }

        cnt = ;

        for(i = ; i <= n; i++)

            if(!out[col[i]]) ans[++cnt] = i;

        sort(ans+, ans++cnt);

        for(i = ; i < cnt; i++) printf("%d ", ans[i]);

        printf("%d\n", ans[cnt]);

    }

    return ;

}

相关文章