校园网络问题

一 原问题链接

Network of Schools - POJ 1236 - Virtual Judgehttps://vjudge.net/problem/POJ-1236

二 输出和输出

1 输入

第1行包含1个整数N，表示网络中学校数。学校由前 N 个正整数标识。接下来的 N 行，每一行都描述了接受者列表，第 i+1 行包含学校 i 的接收者的标识符。每个列表都以0结尾。空列表再行中仅包含0。

2 输出

输出包含两行。第1行应包含子任务1的解，第2行应包含子任务2的解。

三 输入和输出样例

1 输入样例

5

2 4 3 0

4 5 0

0

0

1 0

2 输出样例

1

2

四 思路

1 子任务1

至少发送给多少个学校，才能让软件到达所有的学校呢？实际上，求强连通分量并缩点后，每个入度为0的强连通分量都必须收到一个新的软件副本。

输入样例1，构成的图如下所示，其中包含3个强连通分量，缩点后入度为0的强连通分量有1个，至少发送给1个学校即可，即1、2、5 中的任意一个学校。

2 子任务2

至少添加多少个接收关系，才能实现发送给任意一个学校，所有学校都能收到？也就是说，每个强连通分量都必须有入度，又有出度。对入度为0的强连通分量，，至少添加一个入度；对于出度为0的强连通分量，至少添加一个出度。添加的边数为 max(p，q)，如下图所示。

特殊情况：若只有一个强连通分量，则至少分发给1个学校，需要添加的边数为0。

五 算法设计

1 采用 Targan 算法求解强连通分量，标记连通分量号。

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

3 统计入度为0的连通分量数p及出度为0的连通分量q，求 max(p,q)。

六 代码

package graph.poj1236;

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

public class POJ1236 {
    static final int maxn = 1000 + 5;
    static int n;
    static int head[];
    static int belong[];
    static int cnt;
    static int low[];
    static int dfn[];
    static int out[]; // 节点的出度
    static int in[]; // 节点的入度
    static int num;
    static int id;
    static boolean ins[];
    static Stack<Integer> s = new Stack<>();

    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].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
    }

    /**
     * 功能描述：tarjan 算法
     *
     * @param u 起始节点
     * @author cakin
     * @date 2022/7/3
     */
    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;
            id++;
            do {
                v = s.peek();
                s.pop();
                belong[v] = id;
                ins[v] = false;
            } while (v != u);
        }
    }

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        init();
        for (int i = 1; i <= n; i++) {
            int v;
            while (true) {
                v = scanner.nextInt();
                if (v == 0) {
                    break;
                }
                add(i, 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]) {
                    in[belong[v]]++;
                    out[belong[u]]++;
                }
            }
        if (id == 1) {
            System.out.println(1);
            System.out.println(0);
            return;
        }
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i <= id; i++) {
            if (in[i] == 0)
                ans1++;
            if (out[i] == 0)
                ans2++;
        }
        System.out.println(ans1);
        System.out.println(Math.max(ans1, ans2));
    }
}

class Edge {
    int to;
    int next;
}

七 测试

绿色为输出，白色为输出。