（ 图论专题 ）【 二分图染色 】
二分图的判定方式：图中没有边数为奇数的环。
二分图的另一种等价的说法是，可以把每个节点着以黑色和白色之一，使得每条边的两个端点颜色不同。
不难发现，非连通的图是二分图当且仅当每个连通分量都是二分图，因此我们只考虑无向连通图。
#include<bits/stdc++.h>
#define int long longusing namespace std;const int maxn = 2e5+10;
vector<int> G[maxn];
int via[maxn]; //标记是否染色，一开始为-1
int isp,n,m;void dfs( int u )
{for ( int i=0; i<G[u].size(); i++ ) {int v = G[u][i];if ( via[v]==-1 ) {via[v] = via[u]^1; //没染色则染成相反的dfs(v); //继续深搜}else if ( via[v]==via[u] ) { //如果发现不是二分图说明存在奇圈isp = 0;}}
}signed main()
{memset(via,0,sizeof(via)); isp=1;cin>>n>>m;for ( int i=0; i<m; i++ ) {int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}via[1] = 0;// 起点染成0颜色dfs(1);return 0;
}