1 条题解
-
1
#include<bits/stdc++.h> #define nb 33333 using namespace std; int q, n, m, a[nb]; vector<int> G[nb]; bool bfs(){ a[0] = 0; // 确定原点 queue<int> q; for(int i = 0; i < G[0].size(); i++){ q.push(G[0][i]); a[G[0][i]] = 1 << i; // 确定坐标轴 } while(!q.empty()){ int u = q.front(); q.pop(); for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; if(a[v] != -1) continue; q.push(v); a[v] = 0; for(int j = 0; j < G[v].size(); j++){ int w = G[v][j]; if(a[w] != -1) a[v] |= a[w]; // 将深度恰好小 1 的点编号或起来就是此点编号 } } } for(int u = 0; u < n; u++){ for(int i = 0; i < G[u].size(); i++){ int tmp = a[G[u][i]] ^ a[u]; if(tmp & (tmp - 1)) return 1; // 验证编号方案是否合法 // 如果相邻节点编号异或得到不是 2 的幂,说明方案非法 } } return 0; } int main(){ ios::sync_with_stdio(0); for(cin >> q; q; q--){ cin >> n >> m; memset(a, -1, sizeof(a)); for(int i = 0; i < n; i++) G[i].clear(); for(int i = 0, u, v; i < m; i++){ cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } if((n & (n - 1)) || (m != log2(n) * n / 2) || bfs()){ // n, m 不符合条件或无合法方案,说明原图不是超立方图 cout << "-1\n"; continue; } for(int i = 0; i < n; i++){ cout << a[i] << " "; } cout << endl; } return 0; }
- 1
信息
- ID
- 4187
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 3
- 已通过
- 2
- 上传者