Codeforces Round #589 (Div. 2) D. Complete Tripartite

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 using namespace std;
 7 typedef long long ll;
 8 const int MAXN=1e5+5;
 9 int n,m;
10 vector<int>a[MAXN];
11 void sol(){
12     if(a[1].size()==0){
13         cout<<"-1";
14         return ;
15     }
16     int f1=1,f2=0,f3=0;
17     int color[MAXN];
18     memset(color,0,sizeof(color));
19     f2=a[f1][0];
20     color[1]=1;
21     color[a[f1][0]]=2;
22     for(int j=1;j<=n;j++){     //找到f2和f3
23         bool a1=false,a2=false;
24         for(int i=0;i<a[j].size();i++){
25             if(a[j][i]==f1) a1=true;
26             if(a[j][i]==f2) a2=true;
27         }
28         if(a1&&a2){
29             f3=j;
30             break;
31         }
32     }
33     if(!f3){      //若没有f3则直接输出-1
34         cout<<"-1";
35         return ;
36     }
37     color[f3]=3;
38     for(int i=1;i<=n;i++){   //分到各个集合里
39         int a1=0,a2=0,a3=0;
40         for(int j=0;j<a[i].size();j++){   //检测i点与f1，f2，f3那些点相连
41             if(a[i][j]==f1) a1=1;
42             if(a[i][j]==f2) a2=1;
43             if(a[i][j]==f3) a3=1;
44         }
45         if(a1+a2+a3!=2){    //若不是与其中两个点相连则直接输出-1
46             cout<<"-1";
47             return ;
48         }
49         if(a1&&a2&&!a3) color[i]=3;
50         if(a1&&!a2&&a3) color[i]=2;
51         if(!a1&&a2&&a3) color[i]=1;
52     }
53     int cnt[4]={0};
54     for(int i=1;i<=n;i++) cnt[color[i]]++;      
55     if(cnt[1]*cnt[2]+cnt[2]*cnt[3]+cnt[3]*cnt[1]!=m){       //计算边的数量是否为m
56         cout<<"-1";
57         return ;
58     }
59     for(int i=1;i<=n;i++){       //回路判断，检查每个集合里是否有相连的
60         for(int j=0;j<a[i].size();j++){
61             if(color[i]==color[a[i][j]]){
62                 cout<<"-1";
63                 return ;
64             }
65         }
66     }
67     for(int i=1;i<=n;i++)
68         cout<<color[i]<<" ";
69 }
70 int main(){
71     cin>>n>>m;
72     int x,y;
73     for(int i=0;i<m;i++){
74         cin>>x>>y;
75         a[x].push_back(y);
76         a[y].push_back(x);
77     }
78     sol();
79     return 0;
80 }