链接：

题意：

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G=(V,E) is called a directed graph.

Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1). Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1).

Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

求哪些点能到的点都可以到自己

思路：

一个强连通分量内的点互相可达，所有一个强连通分量没有出度，则这个强连通内的点都满足条件。

代码：

#include <iostream>

#include <cstdio>

#include <vector>

#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

using namespace std;

const int MAXN = 5e3+10;

vector<int> G[MAXN];

stack<int> St;

int Dfn[MAXN], Low[MAXN];

int Dis[MAXN], Vis[MAXN];

int Fa[MAXN];

int times, cnt;

int n, m;

void Tarjan(int x)

{

    Dfn[x] = Low[x] = ++times;

    St.push(x);

    Vis[x] = 1;

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

    {

        int nextnode = G[x][i];

        if (Dfn[nextnode] == 0)

        {

            Tarjan(nextnode);

            Low[x] = min(Low[x], Low[nextnode]);

        }

        else if (Vis[nextnode])

            Low[x] = min(Low[x], Dfn[nextnode]);

    }

    if (Low[x] == Dfn[x])

    {

        cnt++;

        while (St.top() != x)

        {

            Fa[St.top()] = cnt;

            Vis[St.top()] = 0;

            St.pop();

        }

        Fa[St.top()] = cnt;

        Vis[St.top()] = 0;

        St.pop();

    }

}

void Init()

{

    memset(Dis, 0, sizeof(Dis));

    memset(Vis, 0, sizeof(Vis));

    memset(Dfn, 0, sizeof(Dfn));

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

        G[i].clear(), Fa[i] = i;

    times = cnt = 0;

    while (!St.empty())

        St.pop();

}

int main()

{

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

    {

        Init();

        scanf("%d", &m);

        int l, r;

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

        {

            scanf("%d%d", &l, &r);

            G[l].push_back(r);

        }

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

            if (Dfn[i] == 0)

                Tarjan(i);

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

        {

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

            {

                int node = G[i][j];

                if (Fa[i] != Fa[node])

                    Dis[Fa[i]]++;

            }

        }

        int flag = 0;

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

        {

            if (Dis[Fa[i]] == 0)

            {

                if (!flag)

                {

                    printf("%d", i);

                    flag = 1;

                }

                else printf(" %d", i);

            }

        }

        printf("\n");

    }

    return 0;

}

巴特西

POJ-2552-The Bottom of a Graph 强连通分量

链接：

题意：

思路：

代码：

最新文章

热门文章