20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解
debug过程：
- 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。
就是因为数组开小了，导致最后tle了，数组开小了什么报错都有可能出现
- 染色算法能够解决非连通图的二部图判定，所以从一个点dfs出发是不够的，要
多源dfs
也就是说对每个连通块进行dfs,先对一个点dfs后，找此时没有被染色的点再dfs，直到全都被染色或者dfs过程中return false; - 这个dfs过程不需要还原现场，因为我们需要保留所有点的颜色。
- 我的代码中dfs函数只有一个参数，yxc的代码是两个参数，都是可以的？！
#include <bits/stdc++.h>
using namespace std;
//# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int N =1e5+10;
const int M=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;
//int a[N];
int n, m;
int h[N],ne[M],e[M],idx;
bool st[N];
int color[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u){
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!color[j]){
color[j]=3-color[u];
if(!dfs(j)){
return false;
}
}
else {
if(color[j]!=3-color[u])return false;
}
}
return true;
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
memset(h,-1,sizeof h);
int t;
t=1;
//cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
}
bool flag=true;
for(int i=1;i<=n;i++){
if(!color[i]){
color[i]=1;
if(!dfs(i)){
flag=false;
}
}
}
if(flag)cout<<"Yes";
else cout<<"No";
return 0;
}
双参数版的代码
dfs的含义：将u这个点染成c颜色后，返回值是表示会不会出现冲突
#include <bits/stdc++.h>
using namespace std;
//# define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int N =1e5+10;
const int M=2e5+10;
const int inf=0x3f3f3f3f;
const int mod=998244353;
//int a[N];
int n, m;
int h[N],ne[M],e[M],idx;
bool st[N];
int color[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int u,int c){
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(color[j]==0){
if(dfs(j,3-c)==false)return false;
}
else {
if(color[j]==c)return false;
}
}
return true;
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
memset(h,-1,sizeof h);
int t;
t=1;
//cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
}
bool flag=true;
for(int i=1;i<=n;i++){
if(!color[i]){
if(dfs(i,1)==false){
flag=false;
}
}
}
if(flag)cout<<"Yes";
else cout<<"No";
return 0;
}