电话网络问题

一 原问题链接

Network - POJ 1144 - Virtual Judgehttps://vjudge.net/problem/POJ-1144

二 输入与输出

1 输入

输入包含多个测试用例。每个测试用例都描述一个网络。每个测试用例的第 1 行都是 N。接下来最多  N 行中每一行都包含一个地点的编号，后面是该地方可以直达的地点编号。每个测试用例都以一条仅包含0的行结束。N=0时输入结束，不处理。

2 输出

对每个测试用例，都单行输出关键位置的数量。

三 输入样例

5

5 1 2 3 4

0

6

2 1 3

5 4 6 2

0

0

四 输出样例

1

2

五 问题分析

1 输入样例1，构建的图如下。在该图中有1个关键点5。

2 输入样例2，构建的图如下。在该图中有两个关键点，分别是2和5。

本问题就是求割点数，利用 Tarjan 算法求解即可。

六 代码

package graph.poj1144;

import java.util.Scanner;

public class POJ1144 {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int cnt;
    static int root;
    static int low[];
    static int dfn[];
    static int cut[];
    static int num;

    static Edge e[] = new Edge[maxn << 1];

    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) { //求割点
        dfn[u] = low[u] = ++num;
        int flag = 0;
        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]);
                if (low[v] >= dfn[u]) {
                    flag++;
                    if (u != root || flag > 1) {
                        cut[u] = 1;
                    }
                }
            } else
                low[u] = Math.min(low[u], dfn[v]);
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        cut = new int[maxn];
        cnt = num = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            if (n == 0)
                break;
            init();
            int u, v;
            while (true) {
                Scanner scanner1 = new Scanner(System.in);
                String nums = scanner1.nextLine();
                String[] s = nums.split(" ");
                u = Integer.parseInt(s[0]);
                if (u == 0) {
                    break;
                }
                for (int i = 1; i < s.length; i++) {
                    v = Integer.parseInt(s[i]);
                    add(u, v);
                    add(v, u);
                }
            }
            for (int i = 1; i <= n; i++) {
                if (dfn[i] == 0) {
                    root = i;
                    tarjan(i);
                }
            }

            int ans = 0;
            for (int i = 1; i <= n; i++)
                if (cut[i] == 1)
                    ans++;
            System.out.println(ans);
        }
    }
}

class Edge {
    int to;
    int next;
}

七 测试结果

绿色为输入，白色为输出