虽然是T3，但是想通了之后还是不难的。
数据规模也不大。
可以考虑先枚举一个班长，根据题意，和班长连边的学生就可以不用管，没有和班长连边的学生就要去找一个和班长连边的学生组队，如果所有没有和班长连边的学生都能找到一个人组队，就可以。
是一个比较裸的二分图最大匹配。
注意要重新建图，不能直接在原来的图上跑，因为有可能和班长连边的学生之间存在彼此连边的情况，就不符合二分图的定义。
可以另建图跑最大流，也可以就匈牙利，或者$EK$
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<string> 5 #include<queue> 6 #include<algorithm> 7 #include<vector> 8 #include<cstdlib> 9 using namespace std; 10 #define N 1005 11 #define ll long long 12 #define INF 0x3f3f3f3f 13 int n,m; 14 vector<int>G[N],T[N]; 15 bool vis[N],flag[N]; 16 int mch[N]; 17 bool dfs(int u) 18 { 19 for(int i=0;i<T[u].size();i++) 20 { 21 int v=T[u][i]; 22 if(vis[v]) continue; 23 vis[v]=1; 24 if(mch[v]==0||dfs(mch[v])) 25 { 26 mch[v]=u; 27 mch[u]=v; 28 return 1; 29 } 30 } 31 return 0; 32 } 33 int main() 34 { 35 scanf("%d %d",&n,&m); 36 for(int i=1;i<=m;i++) 37 { 38 int u,v;scanf("%d %d",&u,&v); 39 G[u].push_back(v); 40 G[v].push_back(u); 41 } 42 for(int s=1;s<=n;s++)//枚举班长 43 { 44 if(G[s].size()<((n-1)/2)) continue;//如果班长连的学生太少 45 int res=0,num=n-G[s].size()-1/*还有一个自己*/; 46 for(int i=1;i<=n;i++) 47 T[i].clear(),flag[i]=0/*标记是否与班长相连*/,mch[i]=0; 48 mch[s]=-1,flag[s]=1/*防止班长被建到图里面去*/; 49 for(int i=0;i<G[s].size();i++) 50 flag[G[s][i]]=1; 51 for(int i=0;i<G[s].size();i++) 52 { 53 int v=G[s][i]; 54 for(int j=0;j<G[v].size();j++) 55 if(!flag[G[v][j]]) 56 T[v].push_back(G[v][j]); 57 } 58 for(int i=0;i<G[s].size();i++) 59 { 60 memset(vis,0,sizeof(vis)); 61 if(dfs(G[s][i])) 62 res++; 63 } 64 if(res>=num) 65 { 66 puts("Yes"); 67 for(int i=1;i<n;i++) 68 printf("%d ",mch[i]); 69 printf("%d ",mch[n]); 70 return 0; 71 } 72 } 73 puts("No"); 74 return 0; 75 }