图的底部问题

一 原问题链接

The Bottom of a Graph - POJ 2553 - Virtual Judgehttps://vjudge.net/problem/POJ-2553

二 输入和输出

1 输入

输入包含几个测试用例，每个测试用例都对应一个有向图G，每个测试用例都以整数 v开始，表示图 G 的节点数，节点编号为 1~v。接下来是非负整数e，然后是e对编号v1、w1、......ve、we，其中（vi,wi）表示一条边。在最后一个测试用例后跟着一个0.

2 输出

单行输出图底部的所有 sink 节点。如果没有，则输出一个空行。

三 输入和输出样例

1 输入样例

3 3

1 3 2 3 3 1

2 1

1 2

0

2 输出样例

1 3

2

四 问题分析

输入样例1，构建的图如下，图中 sink 节点为 1 和 3。

思路：求解强连通分量，并对强连通分量缩点，计算缩点的出度，出度为0 的强连通分量中的所有节点均为 sink 节点。

五 算法设计

1 先采用 Targan 算法求解有向图的强连通分量，标记强连通分量号。

2 检查每个节点 u 的每个邻接点 v，若强连通分量不同，则将 u 的连通分量号的出度加1。

3 检查每个节点 u，若其连通分量号的出度为0，则输出该节点。

六 代码

package graph.poj553;

import java.util.Scanner;
import java.util.Stack;

public class POJ2553 {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int belong[];
    static int out[];
    static int cnt;
    static int id;
    static int low[];
    static int dfn[];
    static int num;
    static Edge e[] = new Edge[maxn << 1];
    static Stack<Integer> s = new Stack<>();
    static boolean ins[] = new boolean[maxn];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v) { // 添加一条边u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    static void tarjan(int u) { // 求强连通分量
        low[u] = dfn[u] = ++num;
        ins[u] = true;
        s.push(u);
        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (dfn[v] == 0) {
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (ins[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (low[u] == dfn[u]) {
            int v;
            do {
                v = s.peek();
                s.pop();
                belong[v] = id;
                ins[v] = false;
            } while (v != u);
            id++;
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        ins = new boolean[maxn];
        belong = new int[maxn];
        out = new int[maxn];
        cnt = num = 0;
        id = 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            n = scanner.nextInt();
            if (n == 0) {
                return;
            }
            m = scanner.nextInt();
            init();
            while (m-- != 0) {
                int u, v;
                u = scanner.nextInt();
                v = scanner.nextInt();
                add(u, v);
            }
            for (int i = 1; i <= n; i++)
                if (dfn[i] == 0)
                    tarjan(i);
            for (int u = 1; u <= n; u++)
                for (int i = head[u]; i > 0; i = e[i].next) {
                    int v = e[i].to;
                    if (belong[u] != belong[v])
                        out[belong[u]]++;
                }
            int flag = 1;
            System.out.println();
            for (int i = 1; i <= n; i++)
                if (out[belong[i]] == 0) {
                    if (flag == 1)
                        flag = 0;
                    else
                        System.out.print(" ");
                    System.out.print(i);
                }
        }
    }
}

class Edge {
    int to;
    int next;
}

七 测试

绿色为输入，白色为输出