SDUST的训练赛
当时死磕这个水题3个小时,也无心去搞其他的
按照题意,转换成无向图,预处理去掉单向的边,然后判断剩下的图能否构成两个无向完全图(ps一个完全图也行或是一个完全图+一个孤点)
代码是赛后看的网上大神,所以转载过来了,dfs染色的时候很巧妙,巧妙的用到了就两个无向完全图
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=;
int e[maxn][maxn];
int vis[maxn],n;
int bfs(int x)//从x点开始分组。
{
queue<int>q;
q.push(x);
vis[x]=;
int i,j,k,u,v;
while(!q.empty())
{
u=q.front();
q.pop();
for(i=;i<=n;i++)
{
if(e[u][i]==||u==i)continue;
if(vis[i]==-)
{
vis[i]=-vis[u];
q.push(i);
}
else if(vis[i]==vis[u])return ;
}
}
return ;
}
int main()
{
while(cin>>n)
{
int i,j,k,a;
memset(e,,sizeof(e));
memset(vis,-,sizeof(vis));
for(i=;i<=n;i++)
{
while(cin>>a&&a!=)
e[i][a]=;
}
//改成无向图
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(!e[i][j])e[j][i]=;
for(i=;i<=n;i++)
{
if(vis[i]!=-)continue;
if(!bfs(i))break;
}
if(i<=n)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return ;
}
/*
题意:将n个人分成两组,使得每组中的每个人都认识剩余所有人。
用二维数组e记录关系,e[i][j]==0表示i不认识j。
vis[i]表示组别,分别为1和0。则可知若e[i][j]==0 ,则i和j必定是一个是0,一个是1。
bfs一遍,当出现矛盾的时候就不能分组。
由于枚举所有点作起点,且起点为1组内。又e[i][j]=0,e[j][i]=1和e[i][j]=e[j][i]=0情况相同。
为避免起点为1造成的初始化错误,所以讲有向不认识图,改成无向图。例:不认识关系:3->1->2->4,
开始枚举1,则vis[1]=1,vis[2]=0,vis[4]=1,后枚举3,vis[3]=1,vis[1]=0,矛盾,可情况是能分成(3,2)和(1,4)的。
*/