COJ 0578 4019二分图判定

4019二分图判定

难度级别： B；编程语言：不限；运行时间限制：1000ms；运行空间限制：51200KB；代码长度限制：2000000B

试题描述

给定一个具有n个顶点（顶点编号为0，1，……，n-1）的图，要给图上每个顶点染色，并且要使相邻的顶点颜色不同。问是否能最多用2种颜色进行染色？测试数据保证没有重边和自环。

输入

第一行包括两个数n和k，分别表示图的顶点数和边数，接下来有k行，每行有两个整数m1和m2，表示顶点m1和m2间有一条无向边。各行的整数间用一个空格分隔。

输出

如果能就输出1，否则输出0.

输入示例

3 3
0 1
0 2
1 2

输出示例

其他说明

数据范围：1<=n<=1000,发现猜答案的刷题就封号。

题解：染个色。我记得可以用LCT动态维护二分图可惜我忘了QAQ。。。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,inf=-1u>>;

 struct ted{int x,y;ted*nxt;}adj[maxn<<],*fch[maxn],*ms=adj;

 void add(int x,int y){

     *ms=(ted){x,y,fch[x]};fch[x]=ms++;*ms=(ted){y,x,fch[y]};fch[y]=ms++;return;

 }

 bool col[maxn];

 bool color(int x){

     for(ted*e=fch[x];e;e=e->nxt){

         int v=e->y;

         if(!col[v]){col[v]=!col[x];if(!color(v))return false;}

         else if(col[v]==col[x])return false;

     }return true;

 }

 inline int read(){

     int x=,sig=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;

     for(;isdigit(ch);ch=getchar())x=*x+ch-'';

     return sig?x:-x;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 int n,m;

 void init(){

     n=read();m=read();

     for(int i=;i<=m;i++)add(read(),read());

     return;

 }

 void work(){

     col[]=;puts(color()?"":"");

     return;

 }

 void print(){

     return;

 }

 int main(){init();work();print();return ;}

巴特西

COJ 0578 4019二分图判定

最新文章

热门文章