題目連結: https://codeforces.com/problemset/problem/1228/D
# 內容
給出一張簡單圖，其節點數為 n，邊數為 m，判斷此圖是否能構成三分圖 (就是二分圖的強化版)，此圖必須使用三種顏色。若能構成三分圖就將每個節點的顏色輸出，否則輸出 - 1。
# 思路
哈希每一個節點，這樣就能計算出和每個點連接的其他點的總哈希值，
若只有三種哈希值的和，那麼就是符合的～～再用 map 紀錄顏色就好。
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
typedef unsigned long long ull; | |
const int N = 1e5 + 10; | |
ull Hash[N]; | |
int n, m; | |
ull vis[N]; | |
map<ull, int> mp; | |
int main() { | |
int x, y; | |
cin >> n >> m; | |
Hash[0] = 1; | |
for(int i = 1; i <= n; i++) Hash[i] = Hash[i - 1] * 100007; | |
for(int i = 1; i <= m; i++) { | |
cin >> x >> y; | |
vis[x] += Hash[y]; | |
vis[y] += Hash[x]; | |
} | |
int cnt = 1; | |
int flag = 1; | |
for(int i = 1; i <= n; i++) { | |
if(vis[i] == 0) flag = 0; //no connected | |
if(!mp[vis[i]]) mp[vis[i]] = cnt++; | |
vis[i] = mp[vis[i]]; | |
} | |
if(cnt != 4 || !flag) cout << "-1\n"; | |
else for(int i = 1; i <= n; i++) cout<<vis[i]<<" "; cout << '\n'; | |
return 0; | |
} |
