二分图判定
CF687A NP-Hard Problem
假设给定图G。如果对于图中的每条边uv，该集合中至少包含这条边的一个端点（即u或v，或者两者都包含），则称顶点集合A是该图的一个顶点覆盖。
交给你一个图，你需要找到该图的两个不相交的顶点子集A和B，使得A和B都是顶点覆盖，或者声明这是不可能的。
输入
输入的第一行包含两个整数n和m（2≤n≤100,000，1≤m≤100,000），分别表示图中的顶点数和边数。
接下来的m行，每行包含一对整数ui和vi（1≤ui, vi≤n），表示ui和vi之间的一条无向边。保证图中不包含自环或多重边。
输出
如果无法将图分割，则打印“-1”（不包括引号）。
如果存在两个不相交的顶点集合，使得这两个集合都是顶点覆盖，则打印它们的描述。每个描述必须包含两行。第一行包含一个整数k，表示该顶点覆盖中的顶点数，第二行包含k个整数，表示顶点的索引。请注意，由于m≥1，顶点覆盖不能为空。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+10,inf=1e18+10,mod=1000000007;
vector<ll> G[N],c1,c2;
ll n,m,vis[N];
bool ans=true;
void dfs(ll u,ll color){
vis[u]=color;
if(color==1)c1.push_back(u);
else c2.push_back(u);
for(auto v:G[u]){
if(!vis[v])dfs(v,3-color);
else if(vis[v]==color)ans=false;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(ll i=1;i<=m;i++){
ll u,v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for(ll i=1;i<=n;i++){
if(vis[i])continue;
dfs(i,1);
}
if(!ans){
cout << -1;
return 0;
}
cout << c1.size() << endl;
for(auto i:c1)cout << i << ' ';
cout << endl;
cout << c2.size() << endl;
for(auto i:c2)cout << i << ' ';
return 0;
}
ABC327D Good Tuple Problem
给定两个长度均为M的序列，由不超过N的正整数组成，记作(A, B) = ((A_1, A_2, …, A_M), (B_1, B_2, …, B_M))。当这对序列(A, B)满足以下条件时，称它们为一对好的序列对：
存在一个长度为N的序列X = (X_1, X_2, …, X_N)，该序列由0和1组成，并且满足以下条件：
对于每个i = 1, 2, …, M，都有X_A_i ≠ X_B_i。
换句话说，对于序列A和B中的每一对对应位置的元素A_i和B_i，序列X在A_i和B_i位置上的值必须不同。
现在，给定一对这样的序列(A, B)，你需要判断它们是否是一对好的序列对。如果是，输出"Yes"；否则，输出"No"。
约束条件
1 ≤ N, M ≤ 2 × 10^5
1 ≤ A_i, B_i ≤ N
所有输入值都是整数。
#include<bits/stdc++.h>
#define pt printf(">>>")
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
ll n,m,a[N],b[N];
vector<ll> G[N];
ll vis[N];
bool ans=true;
void dfs(ll u,ll color){
vis[u]=color;
for(auto v:G[u]){
if(!vis[v])dfs(v,3-color);
else if(vis[v]==color)ans=false;
}
}
int main(){
cin >> n >> m;
for(ll i=1;i<=m;i++)cin >> a[i];
for(ll i=1;i<=m;i++)cin >> b[i];
for(ll i=1;i<=m;i++){
G[a[i]].push_back(b[i]);
G[b[i]].push_back(a[i]);
}
for(ll i=1;i<=m;i++)if(!vis[i])dfs(i,1);
cout << (ans?"Yes":"No");
return 0;
}