一 原问题描述

From D to E and Back - UVA 11175 - Virtual Judge

https://vjudge.net/problem/UVA-11175

二 输入和输出

1 输入

第1行包括测试用例数N（N<220）。在每个测试用例的前两行都包含 m 和 k，表示图 E 中节点数和边数。下面的 k 行，每行都包含两个节点 x 和 y，表示在 E 中从 x 到 y 有一条边。节点编号从 0 ~ m-1。

2 输出

对每个测试用例，都输出一行 Case #t，t表示测试用例编号，然后是 Yes 或者 No，用于判断 E 是否是一个有向图 D 的 Lying 图。

3 输入样例

4

2

1

0 1

5

0

4

3

0 1

2 1

2 3

3

9

0 1

0 2

1 2

1 0

2 0

2 1

0 0

1 1

2 2

4 输出样例

Case #1: Yes

Case #2: Yes

Case #3: No

Case #4: Yes

三 问题分析

本问题实际上就是把 D 中的边缩成点，D 中的一条边对应 E 中的一个节点，如果在 D 中存在边i（u、v）和 j（v、w），则 E 将具有从节点 i 到节点 j 的边。

如果在 D 中边 i 和边 j 有公共端点，则 i 连接的边，j 一定也连接，不存在 i 连接的边但是 j 没连接的情况。那么在 E 中，节点 i 和节点 j 有公共邻接点，则 i 邻接的节点，j 一定也邻接。如下图所示，在 D 中，边 i 和边 j 有公共端点 c，i 连接边 k1 和 k2，j 则一定也连接边 k1、k2；在对应的 E 中，节点 i 和节点 j 有公共邻接点 k1，i 有邻接点 k2，j 则一定也有邻接点 k2。

四 算法设计

1 用邻接矩阵存储 E。

2 判断在 E 中是否存在节点 i 和节点 j 有公共邻接点，如果存在，再判断是否存在对 i 有邻接的节点但是对 j  没有邻接的节点的情况，如果存在，就说明该 E 图不是一个有向图 D 的 Lying 图。

五 代码实现

package graph;

import java.util.Scanner;

public class UVA11175 {
    static final int maxn = 300 + 5;
    static int n;
    static int m;

    static boolean solve(int g[][]) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                boolean flag1 = false, flag2 = false;
                for (int k = 0; k < n; k++) {
                    if (g[i][k] == 1 && g[j][k] == 1) // i=0 j=2  k=1
                        flag1 = true;
                    if (g[i][k] != g[j][k])
                        flag2 = true;
                }
                if (flag1 && flag2)
                    return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int T, cnt = 0, x, y;
        Scanner scanner = new Scanner(System.in);
        int g[][] = new int[maxn][maxn];
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            x = scanner.nextInt();
            y = scanner.nextInt();
            g[x][y] = 1;
        }
        if (solve(g))
            System.out.println("Case #" + ++cnt + ": Yes");
        else
            System.out.println("Case #" + ++cnt + ": No");
    }
}

六 测试

绿色为输入，白色为输出