如题: 模板保存.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- const int maxn=1e5+5;
- const int maxm=1e5+5;
- int c[maxn]; //color, 每个点的黑白属性,-1 表示还没有标记, 0/1 表示黑白, 比 vis 数组多一个作用
- int num[2]; // 在一次 DFS 中的黑白点个数
- bool f=0; // 判断是否出现奇环
- int head[maxn],tot,n,m;
- struct edge{
- int to;
- int nxt;
- }e[maxm];
- void add_edge(int u,int v){
- e[tot].to=v;
- e[tot].nxt=head[u];
- head[u]=tot++;
- }
- void init(){
- memset(head,-1,sizeof head);
- tot=0;
- memset(c,-1,sizeof c);
- }
- void dfs(int u,int x){
- if(f)return;
- c[u]=x;
- num[x]++;
- for(int i=head[u];~i;i=e[i].nxt){
- int j=e[i].to;
- if(c[j]==-1) dfs(j,!x);
- else if(c[j]==x){// 冲突了, 不冲突则跳过.
- f=1;
- return;
- }
- }
- }
- int main(){
- for(int i=1;i<=n&&(!f);i++){
- if(c[i]==-1){
- num[0]=num[1]=0;
- dfs(i,1);
- }
- }
- }
[模板] 黑白染色
来源: http://www.bubuko.com/infodetail-2947793.html