2014-07-28

UVa 11785 - Hypercube

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

In geometry, a hypercube is an n-dimensional analogue of a square (n = 2) and a cube (n = 3). It consists in groups of opposite parallel line segments aligned in each of the space’s dimensions, at right angles to each other and of the same length. An n-dimensional hypercube is also called an n-cube.

\epsfbox{p11785.eps}

In parallel computing, the vertexes are processors, and the line segments (edges) represent connections. The n-cube architecture has the following properties:

Each node has n connections with different processors.
Each processor has a unique identifier, between 0 and 2n - 1.
Two processors are directly connected if and only if their identifiers differ in just one bit. For instance, in a 3-cube, processors 3 (011 in binary) and 7 (111 in binary) are directly connected.
The number of processors is 2n

The new company WEFAIL is designing hypercubes, but they are always contracting new people, whose do not know all the hypercube properties, and sometimes they fail; thus these properties are not satisfied in all cases. Given an arbitrary graph, your task is to write a program that determines whether the graph is a hypercube or not.

Input

The input consists in several problem instances. Each instance contains one graph, which starts with a line with two positive integers: K and M, representing the number of vertexes ( 0 < K$\le$1024) and the number of edges respectively. It follows ( 0$\le$M$\le$5130) lines, representing the edges. Each edge is given by two 32 bits integers, representing the processors connected by the edge.

The end of input is indicated by a test case with K = 0.

Output

For each problem instance, the output is a single line, with the word YES if the corresponding graph is a hypercube, and NO otherwise (quotes for clarity). The output must be written to standard output.

Sample Input

Sample Output

1
2
3

YES
NO
NO

Solution

題目描述：

判斷是否與超立方體同構

題目解法：

原本使用貪心的映射方式，然後進行超立方體的判斷，但是這樣的條件不好撰寫，其中肯定有 BUG。

最後使用全局最短路總和會相同的方式，還真是各種邪惡的題目。然而題目假使會有超出節點的編號，直接忽略報錯即可。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
vector<int> g[1024];
int bfs(int n) {
    int visited[1024] = {};
    int u, v, ret = 0;
    queue<int> Q;
    Q.push(0), visited[0] = 1;
    while(!Q.empty()) {
        u = Q.front(), Q.pop();
        for(int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if(visited[v] == 0) {
                visited[v] = visited[u] + 1;
                ret += visited[u];
                Q.push(v);
            }
        }
    }
    return ret;
}
int main() {
    int n, m, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        for(int i = 0; i < n; i++)
            g[i].clear();
        int size = 0, eflag = 0;
        for(int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            if(x >= 0 && x < n && y >= 0 && y < n) {
                g[x].push_back(y);
                g[y].push_back(x);
            } else {
                eflag = 1;
            }
        }
        for(m = 0; (1<<m) < n; m++);
        for(int i = 0; i < n; i++)
            if(g[i].size()%m)
                eflag = 1;
        if((n&(-n)) != n || eflag) {
            puts("NO");
            continue;
        }
        int ret = 0, ac = 0;
        for(int i = 0; i < n; i++)
            ret += bfs(i);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t = i^j;
                ac += __builtin_popcount(t);
            }
        }
        puts(ret == ac ? "YES" : "NO");
    }
    return 0;
}

Morris' Blog