题意:给你n，m表示有n个点编号从1到n，然后m条边；问这个图是否能形成一个三分图； 那么什么是三分图呢？我相信如果知道二分图的，三分图肯定就知道了；因为二分图是把图上的点分为两个集合1,2；并且对于集合1中任意点都要和集合2中的任意点有边相连接，并且满足对集合本身中的点之间没有边相互连接；其实三分图也是类比这个思想来的； 也就是三个集合1,2,3，问是否能构成任意两个集合之间的元素能有边相连接，并且集合自己本身中的点没有边连接； 其实这个题虽然题目给了没有自回路，但是为什么后面我明明分为三个集合了为什么还是wa呢? 后来我自己加了自回路的判断条件才过的，所以我觉得测试数据应该包含了自回路的测试数据，虽然题上说没有自回路！！！！ 我先来说说我自己的思路吧： 1.首先利用邻接表建立无向图； 2.把1点设为属于集合1，同时判断是否它是和其他点相连接，如果没有和1相连接的点，那么肯定答案就是-1了；为什么呢？ 因为： 这种能构成三分图吗？ 显然不行； 3.任意找出一个与1点相连接的点，我假设成2点哈，因为这个取点是按照输入顺序来的； 那么这个2点肯定不会和1点是一个集合；为什么呢？ 因为： 因为一个集合里面任意两点之间不能存在边相连接； 所以我把2点设为集合2； 3.找出于1点和2点相连接的 其他点我假设为3点，其实也可以是其他点，我这里方便描述就这样说了； 注意这里找的时候，需要知道与1点和2点相连接的点，肯定只能是与1点和2点相连接； 因为题给的图可能会有这四种情况： 所以很明显只能第一种才能够满足三分图；所以在for的时候需要判断是否能找出第三个点，使得第三个点同时连接1,2两个点； 4.到这一步说明前面的1，2,3集合中 都有一个点了，并且这些点是两两相连接的；现在需要做的就是去吧其他点给分别加入三个不同的集合，那么就有三种情况： 1.枚举到当前这个点的时候这个点和1,2点相连接，与3不连接，加入集合3； 2.枚举到当前这个点的时候这个点和1,3点相连接，与2不连接，加入集合2； 3.枚举到当前这个点的时候这个点和2,3点相连接，与1不连接，加入集合1； 所以费力的就完了； 最后需要知道一个只是：对于三分图的特点(我感觉好像性质！！)： 比如案例这个： 有三个集合第一个集合有1个点，第二个集合有2个点，第三个集合有3个点； 那么他们构成的边数就是12+23+31这个数字必须等于题上给的m才满足题意！！！！ 其实二分图也是这样算的边数吧！！！ 其实这个也好理解，你可以这样理解： 比如集合2和集合3； 在集合2中是不是2对应4,5,6三个？ 在集合2中是不是3对应4,5,6三个？ 所以他们之间的边总数肯定等于23咯； 所以是很好理解吧！！ 最后就是最坑的地方了； 我觉得自己构造出的集合中是没有边相连接的； 但是一直wa，最后加一个判断自回路就过了； 我觉得案例应该有自回路数据，而不是题上说的没有自回路吧； AC代码：
#include<bits/stdc++.h> using namespace std; const int M=100050; vector<int> edge[M]; int color[M]; int cnt[5]; int main(){ int n,m; int a,b; scanf("%d %d",&n,&m); for(int i=0;i<m;i++){//建立无向图 scanf("%d %d",&a,&b); edge[a].push_back(b); edge[b].push_back(a); } if(edge[1].size()==0){//如果点1 没有出度，那么肯定就不能构成三分图 cout<<-1<<endl; return 0; } int first=1;//把1设为第一个集合 color[first]=1; int second=edge[first][0];//找出与第一个点相连的点 color[second]=2;//把这个与1相连的点给设为集合2中； //遍历那些点与1和2相连接 int three=0; for(int i=2;i<=n;i++){//因为第一个点 不需要自己找自己 int f1=0,f2=0; for(int j=0;j<edge[i].size();j++){//这两个for就很巧妙了；因为我当时怎么也没想到去遍历第三个点使得和1,2两个点相连接！！！！！ int t=edge[i][j]; if(t==first) f1=1; if(t==second) f2=1; } if(f1&&f2){ three=i; color[three]=3; break;//找出一个 与1和2集合相连接的点作为集合3 } } if(!three){//如果没有找到第三个点与1,2点相连接，那么肯定就不能构成三分图了 cout<<-1<<endl;return 0; } //找 1.与1 2相连接但是与3 不相连接的点 2.找与1 3 连接的但是不和2连接的点 3.找与2 3连接的点但是不和1连接的点 for(int i=1;i<=n;i++){ int f1=0,f2=0,f3=0; for(int j=0;j<edge[i].size();j++){ int t=edge[i][j]; if(t==first) f1=1; if(t==second) f2=1; if(t==three) f3=1; } if(f1+f2+f3!=2){ cout<<-1<<endl;return 0; } if(f1&&f2&&!f3)color[i]=3; if(f1&&f3&&!f2)color[i]=2; if(!f1&&f2&&f3) color[i]=1; } for(int i=1;i<=n;i++)cnt[color[i]]++;//这里用来记录 每个集合有多少个点 if(cnt[1]*cnt[2]+cnt[2]*cnt[3]+cnt[3]*cnt[1]!=m){//这里用来算边数 cout<<-1<<endl;return 0; } for(int i=1;i<=n;i++){//这里用来检查自回路 for(int j=0;j<edge[i].size();j++){ if(color[i]==color[edge[i][j]]){ cout<<-1<<endl; return 0; } } } for(int i=1;i<=n;i++){ printf("%d%c",color[i],i==n?'\n':' '); } return 0; }