Bottom problem of figure

One   Link to original question

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

Two   Input and output

1  Input

The input contains several test cases , Each test case corresponds to a directed graph G, Each test case is expressed as an integer  v Start , Diagram  G  Of nodes , Node number is 1~v. Next, nonnegative integers e, And then there was e To number v1、w1、......ve、we, among （vi,wi） To represent an edge . The last test case is followed by 0.

2  Output

Output all at the bottom of the diagram in a single line  sink  node . without , Then output a blank line .

3、 ... and   Input and output examples

1  sample input

3 3

1 3 2 3 3 1

2 1

1 2

0

2  sample output

1 3

2

Four   Problem analysis

sample input 1, The constructed figure is as follows , In the figure  sink  The node is 1  and 3.

Ideas ： Find the strongly connected component , And shrink points for strongly connected components , Calculate the output of the shrink point , The degree of 0  All nodes in the strongly connected component of are  sink  node .

5、 ... and   Algorithm design

1  First use  Targan  The algorithm solves the strongly connected components of a directed graph , Mark the strongly connected component number .

2  Check each node  u  Every adjacent point of  v, If the strongly connected components are different , Will  u  The output of the connected component number of plus 1.

3  Check each node  u, If the degree of its connected component number is 0, Then output the node .

6、 ... and   Code

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) { //  Add an edge u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    static void tarjan(int u) { //  Find the strongly connected component 
        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;
}

7、 ... and   test

Green is the input , White is the output