单位网站建设目的/关键词免费

前言

$tag:$二分图 非连通图 染色法

传送门 :

题意 :
给定一个$n$,和$n$个数对,{a,b}\{a,b\}{a,b},询问是否可以将这些数对分为两组使得每组中不出现相同的数字

思路 :
我们考虑{a,b}\{a,b\}{a,b}之间建立一条边,如果不存在每组中相同的数字,那么必然不可能出现这种情况,这种情况可以继续扩大即 奇数环。

我们可以从 二分图中得知, 二分图恰好没有奇数环

显然的,如果每个连通分量都没有奇数环,那么是可以任意分配的

因此我们只需要对每个连通分量跑一遍 $dfs染色法$

code :

#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
#define cer(a) cerr<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" "<<endl
typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;struct node{int to,val;
};int st[N];
int n,cnt[N];
int i,j;
vector<int> g[N];bool dfs(int u,int col){st[u] = col;for(auto x : g[u]){if(!st[x])	//1 2 染色 dfs(i,1){if(!dfs(x,3-col)) return false;}else if(st[x] == col) return false;}return true;
}void init(){Fup(i,1,n){g[i].clear();st[i] = 0 ;cnt[i] = 0 ;}
}
void solve(){cin>>n;	init();int flag = 0 ;Fup(i,1,n){int l,r;cin>>l>>r;cnt[l] ++ ,cnt[r]++;if(l == r){flag = 1;}g[l].pb(r);g[r].pb(l);}if(flag){cout<<"NO"<<endl;return;}Fup(i,1,n){if(cnt[i] != 2){cout<<"NO"<<endl;return;}}Fup(i,1,n){if(!st[i]){if(dfs(i,1) == false){cout<<"NO"<<endl;return;}}}cout<<"YES"<<endl;}int main(){IOSCITCOTint t;cin>>t;while(t--)solve();return 0 ;
}