如果一张无向图的N个结点可以分成A,B两个非空集合，其中A∩B=∅A\cap B=\emptysetA∩B=∅，并且在同一集合内的点之间都没有边相连，则称这张图为二分图。

二分图判定

定理：一张图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。

P1330 封锁阳光大学

染色法判定：尝试用黑白两色标记，当一个结点被标记后，它的所有相邻结点应该被标记与之相反的颜色，若该标记过程中出现冲突，则说明图中存在奇环。

下用BFS、DFS、并查集分别实现。

BFS

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int head[N],ver[M],nex[M],vis[N];
int n,m,u,v,tot=0,ok=1;
int sum[5],ans;void add(int u,int v)
{ver[++tot]=v;nex[tot]=head[u];head[u]=tot;
}bool bfs(int start,int color)
{queueq;q.push(start);vis[start]=color;//printf("vis[%d]=%d\n",start,vis[start]);sum[1]=1,sum[2]=0;//初始化while(q.size()){int now=q.front();q.pop();for(int i=head[now];i;i=nex[i]){int to=ver[i];if(vis[to]==0) {if(vis[now]==1) vis[to]=2,sum[2]++;else vis[to]=1,sum[1]++;//printf("vis[%d]=%d\n",to,vis[to]);q.push(to);}else if(vis[to]==vis[now]) return false;}}return true;
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v),add(v,u);}for(int i=1;i<=n;i++){if(vis[i]) continue;//vis[i]==0的话表明跟之前的结点都不连通 if(!bfs(i,1)){ok=0;break;}else ans+=min(sum[1],sum[2]);//加和}if(ok) cout<

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int head[N],ver[M],nex[M],vis[N];
int n,m,u,v,tot=0,ok=1;
int sum[5],ans;void add(int u,int v)
{ver[++tot]=v;nex[tot]=head[u];head[u]=tot;
}bool dfs(int now,int color)
{for(int i=head[now];i;i=nex[i]){int to=ver[i];if(!vis[to]) {if(vis[now]==1) vis[to]=2,sum[2]++;else vis[to]=1,sum[1]++;dfs(to,vis[to]);}else if(vis[to]==vis[now]) return false;}return true;
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v),add(v,u);}for(int i=1;i<=n;i++){if(vis[i]) continue;//vis[i]==0的话表明跟之前的结点都不连通 sum[1]=1,sum[2]=0;vis[i]=1;if(!dfs(i,1)){ok=0;break;}else ans+=min(sum[1],sum[2]);//加和}if(ok) cout<

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int f[N*2],size[N];
int n,m,x,y,tot=0,ok=1;int find(int x)
{if(f[x]==x) return f[x];else return f[x]=find(f[x]);
}int main()
{cin>>n>>m;for(int i=1;i<=2*n;i++)f[i]=i;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);int fx1=find(x),fy1=find(y);int fx2=find(x+n),fy2=find(y+n);if(fx1==fy1){ok=0;break;}else f[fx2]=fy1,f[fy2]=fx1;}if(ok) cout<<"OK"<

#include
using namespace std;
const int N=1e4+10,M=2e5+10;
int f[N*2],size[N*2],mem[N*2],h[N];
//1~n白染色域，n+1~2n黑染色域 
int n,m,x,y,tot=0,ok=1,ans;int find(int x)
{if(f[x]==x) return f[x];else return f[x]=find(f[x]);
}
void merge(int x,int y)
{int fx=find(x);if(fx!=y){f[y]=fx;size[fx]+=size[y];}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i,size[i]=1;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);//每条边的两个顶点必不在一个染色域 int fx=find(x),fy=find(y);if(fx==fy)//在同一个染色域 {cout<<"Impossible"<if(h[x]) merge(h[x],fy);if(h[y]) merge(h[y],fx);h[x]=fy,h[y]=fx;}}for(int i=1;i<=n;i++){int q=find(i);if(!mem[q])//一个未处理过的并查集 {int p=find(h[i]);mem[p]=mem[q]=1;ans+=min(size[p],size[q]);//两域取其小 }}cout<

#include
using namespace std;
const int N=520;
int n,m,e,tot,ans;
int mp[N][N],vis[N],match[N];bool dfs(int x)
{for(int i=1;i<=m;i++){if(!mp[x][i]||vis[i]) continue;vis[i]=1;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}return false;
}int main()
{cin>>n>>m>>e;for(int i=1;i<=e;i++){int x,y;scanf("%d%d",&x,&y);mp[x][y]=1;}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i)) ans++;}cout<