【UVA 11175】From D to E and Back 题解（图论）

取具有n个顶点和m条边的任意有向图D。你可以在 以下方式。E将有m个顶点，每个顶点对应于D的每条边。例如，如果D有一条边uv， 那么E将有一个叫做uv的顶点。现在，每当D有边uv和vw时，E就会有边 顶点uv到顶点vw。E中没有其他边。 你将得到一张E图，并且必须确定E是否有可能是某些有向图D的图的卧图。

输入 第一行输入给出了案例数N（N<220）。接下来是N个测试用例。每一个都开始 其中两条线包含m（0≤m≤300）和k。接下来的k条线将分别包含一对顶点， x和y，这意味着E中有一条从x到y的边。顶点的编号从0到m−1 输出 对于每个测试用例，输出一行包含“case#x:”，后跟“Yes”或“No”，具体取决于 无论E是否是有效的卧图。注意，D允许有重复边和自边。

Sample Input 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 Sample Output Case #1: Yes Case #2: Yes Case #3: No Case #4: Yes

思路

易知节点a,b,c,d，若a->c且b->c，则必有a->d，b->d

AC代码

#include <iostream>
#include <cstring>
using namespace std;
#define AUTHOR "HEX9CF"

const int maxn = 305;

// 邻接矩阵
int matrix[maxn][maxn];

void read(int &x)
{
    char ch;
    x = 0;
    while (!('0' <= ch && '9' >= ch))
    {
        ch = getchar();
    }
    while (('0' <= ch && '9' >= ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int check(int m)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int a = 0;
            int b = 0;
            for (int k = 0; k < m; k++)
            {
                // i -> a 且 j -> a
                if (matrix[i][k] && matrix[j][k])
                {
                    a = 1;
                }
                // i -> b 但 j !-> b
                if (matrix[i][k] ^ matrix[j][k])
                {
                    b = 1;
                }
            }
            if (a && b)
            {
                return 0;
            }
        }
    }
    return 1;
}

int main()
{
    int n;
    read(n);
    for (int cnt = 1; cnt <= n; cnt++)
    {
        int m, k;
        memset(matrix, 0, sizeof(matrix));
        read(m); // 节点数
        read(k); // 边数
        for (int i = 0; i < k; i++)
        {
            int u, v;
            read(u);
            read(v);
            matrix[u][v] = 1;
        }
        cout << "Case #" << cnt << ": ";
        if (check(m))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}