502
cf 167.div2 E.Dima and Horses
题意很简单，就是分组，让冲突最多有一种，因为只要分成2组，就是个2-SAT
但是最多只有3个不和，就是不和的三个里至少有2个在一组，所以应该必然有解（这边不太明白，感觉这样），直接染色就可以了
/*
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 <queue>
#define INF 1E9
using namespace std;
int en[300010][3];
int d[300010];
bool ok[300010];
bool sat(int v)
{
int i,now=0,u;
for(i=0;i<d[v];i++)
{
u=en[v][i];
if(ok[u]==ok[v])now++;
}
if(now>1)
{
ok[v]=!ok[v];
for(i=0;i<d[v];i++)
{
u=en[v][i];
if(ok[v]==ok[u])sat(u);
}
}
}
int main()
{
int n,m,i,a,b;
scanf("%d%d",&n,&m);
memset(d,0,sizeof(d));
memset(ok,0,sizeof(ok));
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
en[a][d[a]++]=b;
en[b][d[b]++]=a;
}
for(i=1;i<=n;i++)
sat(i);
for(i=1;i<=n;i++)
printf("%d",ok[i]);
puts("");
}
最后更新：2017-04-04 07:03:49