思路：
任选一点a，和a没有边直接相连的点一定和a在同一个集合，由此构造得到一个集合A。用类似的方法再构造一个集合B，并将剩下的点放在集合C中，就得到了三个集合A，B，C。再检查A，B，C是否符合要求即可。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100005; 4 vector<int> G[N]; 5 int res[N]; 6 int main() 7 { 8 int n, m; 9 while (cin >> n >> m) 10 { 11 for (int i = 1; i <= n; i++) { res[i] = 0; G[i].clear(); } 12 int a, b; 13 for (int i = 0; i < m; i++) 14 { 15 cin >> a >> b; 16 G[a].push_back(b); 17 G[b].push_back(a); 18 } 19 res[1] = 1; 20 set<int> st{G[1].begin(), G[1].end()}; 21 for (int i = 2; i <= n; i++) 22 { 23 if (!st.count(i)) res[i] = 1; 24 } 25 int i = 2; 26 for ( ; i <= n; i++) 27 { 28 if (res[i] != 1) break; 29 } 30 res[i] = 2; 31 set<int> st2{G[i].begin(), G[i].end()}; 32 for (int j = 2; j <= n; j++) 33 { 34 if (j == i || res[j] == 1) continue; 35 if (st2.count(j)) res[j] = 3; 36 else res[j] = 2; 37 } 38 vector<int> c(4, 0); 39 for (int i = 1; i <= n; i++) c[res[i]]++; 40 bool flg = true; 41 if (!c[1] || !c[2] || !c[3]) flg = false; 42 if (m != c[1] * c[2] + c[2] * c[3] + c[3] * c[1]) flg = false; 43 for (int i = 1; i <= n; i++) 44 { 45 int p = res[i]; 46 for (auto it: G[i]) 47 { 48 if (res[it] == p) { flg = false; break; } 49 } 50 if (!flg) break; 51 } 52 if (!flg) { cout << -1 << endl; continue; } 53 for (int i = 1; i <= n; i++) cout << res[i] << " "; 54 cout << endl; 55 } 56 return 0; 57 }