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