621
hdu 4751 Divide Groups 染色
建个反向图，染个色，一切不言而喻
今天比赛一直把题目想复杂，没改题前先求了重联通图，改题后又试了极大团，2sat等等。还是基础不牢，概念不清
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int n;
int MM[101][101];
int org[101][101];
int color[101];
int dfs(int v,int c)
{
if(!color[v])color[v]=c;
else
{
if(color[v]==c)return 0;
else return 1;
}
for(int i=1;i<=n;i++)
if(org[v][i]&&v!=i)
if(dfs(i,-c))return 1;
return 0;
}
int solve()
{
memset(color,0,sizeof(color));
for(int i=1;i<=n;i++)
if(!color[i])
if(dfs(i,1))return 0;
return 1;
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
int t;
memset(MM,0,sizeof(MM));
for(i=1; i<=n; i++)
while(~scanf("%d",&t)&&t)
MM[i][t]=1;
memset(org,0,sizeof(org));
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
if(!MM[i][j]||!MM[j][i])
org[i][j]=org[j][i]=1;
if(solve())puts("YES");
else puts("NO");
}
}
最后更新：2017-04-03 15:21:46