·判断二分图（染色）

#include<bits/stdc++.h>
using namespace std;
void __p(int x) {cerr<<x;}
void __p(long long x){cerr<<x;}
void __p(long double x){cerr<<x;}
void __p(double x){cerr<<x;}
void __p(string s){cerr<<s;}
void __p(char s){cerr<<s;}
void _print(){cerr<<"]\n";}
template<typename T,typename... V>//定义类模版
void _print(T t,V... v){__p(t);if(sizeof...(v))cerr<<",";_print(v...);}
#define debug(x...) cerr<<"["<<#x<<"] = ["; _print(x);
#define see1 cout<<"-------------\n";
#define see2 cerr<<"-------------\n";
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define double long double
#define sqrt sqrtl
/*1.进行移位运算时, 1LL<<n ,1后面不要忘了LL否则会溢出
2.数组开太大放到外面,作为全局数组
3.dfs递归深度超过几千层可能会溢出*/
const int N=2e5+10;
int a[N],n,m,vis[N],f=1;
vector<int>g[N];void dfs(int x){for(auto y:g[x]){if(vis[y]==0){a[y]=(a[x]^1);vis[y]=1;dfs(y);}else if((a[y]^1)!=a[x]){// debug(x,y);f=0; return; }}
}void solve()
{cin>>n>>m;vector<int>a(m+10),b=a;for(int i=1;i<=m;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}for(int i=1;i<=m;i++){int x=a[i];int y=b[i];g[x].push_back(y);g[y].push_back(x);}for(int i=1;i<=n;i++){if(!vis[i])dfs(i);}if(f)cout<<"Yes";elsecout<<"No";}signed main()
{ioint t=1;// cin>>t; while(t--){solve();}
}

 

· 妙妙构造

 

#include<bits/stdc++.h>
using namespace std;
void __p(int x) {cerr<<x;}
void __p(long long x){cerr<<x;}
void __p(long double x){cerr<<x;}
void __p(double x){cerr<<x;}
void __p(string s){cerr<<s;}
void __p(char s){cerr<<s;}
void _print(){cerr<<"]\n";}
template<typename T,typename... V>//定义类模版
void _print(T t,V... v){__p(t);if(sizeof...(v))cerr<<",";_print(v...);}
#define debug(x...) cerr<<"["<<#x<<"] = ["; _print(x)
#define see1 cout<<"-------------\n";
#define see cerr<<"-------------\n";
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define double long double
#define sqrt sqrtl
const int inf = 8e18;
const int N=2e5+10;
vector<pair<int,int>>g[N];
int p[N],tot,n,m,a[N],d[N],cnt[2],vis[N];void dfs(int u){p[++tot]=u;for(auto [v,w]:g[u]){if(!vis[v]){vis[v]=1;d[v]=(d[u]^w);dfs(v);}else if(d[v]!=(d[u]^w)){cout<<-1;exit(0);}}
}void solve(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w; cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=1;tot=0;dfs(i);for(int k=0;k<30;k++){cnt[0]=cnt[1]=0;for(int j=1;j<=tot;j++){cnt[((d[p[j]]>>k)&1)]++;}if(cnt[1]>cnt[0])a[i]+=(1<<k);}for(int j=1;j<=tot;j++){a[p[j]]=(a[i]^d[p[j]]);}}}for(int i=1;i<=n;i++)cout<<a[i]<<' ';}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//  cin>>t;while(t--){solve();}
}

 ·确保图是二分图的情况下添边

 

#include<bits/stdc++.h>
using namespace std;
const int N=120;
int c[N],n;
vector<int>g[N];void dfs(int u,int fa){for(auto v: g[u]){if(v==fa) continue;c[v]=(c[u]^1);dfs(v,u);}
}signed main(){cin>>n;for(int i=1;i<n;i++){int x,y; cin>>x>>y; g[x].push_back(y);g[y].push_back(x);}dfs(1,-1);set<pair<int,int>>s;// for(int i=1;i<=n;i++)// cout<<c[i]<<' ';// cout<<endl;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(c[i]==c[j]) continue;s.insert({i,j});// cerr<<i<<' '<<j<<endl;}}for(int i=1;i<=n;i++){for(auto j: g[i]){if(j<i) continue;s.erase({i,j});}}if(s.size()&1){cout<<"First"<<endl;while(1){cout<<s.begin()->first<<' '<<s.begin()->second<<endl;s.erase(s.begin());int x,y; cin>>x>>y; if(x==-1) break;s.erase({x,y});}}else{cout<<"Second"<<endl;while(1){int x,y;cin>>x>>y; if(x==-1) break;s.erase({x,y});cout<<s.begin()->first<<' '<<s.begin()->second<<endl;s.erase(s.begin());            }}}

 25/3/24