POJ 2553 The Bottom of a Graph（强连通分量的出度）

题意：

求出图中所有汇点

定义：点v是汇点须满足 --- 对图中任意点u，若v可以到达u则必有u到v的路径；若v不可以到达u，则u到v的路径可有可无。

模板:http://www.cnblogs.com/Jadon97/p/8328750.html

分析：

很显然，图中强连通分量中所有的点属性都是一样的，要么都是汇点，要么都不是。

如果有一个强连通分量A的边连向强连通分量B，那么A一定不是汇点，因为B不会有边连向A（如果有的话A、B就是同一个强连通分量了）。

求出所有强连通分量，然后再求一下出度即可

#include <stack>

#include <cstdio>

#include <vector>

#include <iostream>

#include <cstring>

using namespace std;

const int maxn = ;

vector<int> G[maxn];

int n , m;

int dfn[maxn], low[maxn], color[maxn], out_degree[maxn];

int dfs_num = , col_num = ;

bool vis[maxn];//标记元素是否在栈中

stack<int> s;

void Tarjan(int u)

{

    dfn[ u ] = dfs_num;

    low[ u ] = dfs_num++;

    vis[u] = true; //标记访问

    s.push(u); // 入栈

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

    {

        int v = G[u][i];

        if( ! dfn[v])

        {

            Tarjan( v );

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

        }

        else if(vis[v]) //如果在v栈中 ， 更新low[u]

        {

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

        }

    }

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

    {

        vis[u] = false;

        color[u] = col_num;

        int t;

        for(;;){

            int t = s.top(); s.pop();

            color[t] = col_num;

            vis[t] = false;

            if(t == u) break;

        }

        col_num++;

    }

}

int main()

{

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

    {

        if(n == ) break;

        for(int i = ; i < maxn; i++) G[i].clear();

        memset(dfn,  , sizeof(dfn));

        memset(vis,  , sizeof(vis));

        memset(low,  , sizeof(low));

        memset(color, , sizeof(color));

        memset( out_degree,  ,sizeof(out_degree));

        dfs_num = , col_num = ;

        for(int i = ; i < m; i++)

        {

            int u , v;

            scanf("%d %d", &u, &v);

            G[u].push_back(v);

        }

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

            if(!dfn[i])

                Tarjan(i);

        }

        for(int u = ; u <= n; u++){ //

            for(int i = ; i <  G[u].size(); i++){//枚举每一条边

                int v = G[u][i];

                if(color[u] != color[v]){ //如果有一条u到v的边， 但u，v不是同一个强连通分量， 说明u所在的强连通分量有一条出边指向v， u中都不是题目所求

                    out_degree[color[u]]++;

                }

            }

        }

        int cnt = , ans[maxn];

        for(int u = ; u <= n; u++){

            if(out_degree[color[u]] == ) ans[cnt++] = u;

        }

        printf("%d",ans[]);

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

    }

    return ;

}

巴特西

POJ 2553 The Bottom of a Graph（强连通分量的出度）

题意：

分析：

最新文章

热门文章