题目链接：https://codeforc.es/contest/1702/problem/E

第一次cf周赛做到了图论的题，真的挺开心的。

这道题题的大意就是，给出一个数n，然后给出n对数a，b。让我们构造两组数，这两组数的元素都是1-n，且没有重复元素。

solution：利用并查集判重，当一个元素被奇数个数视为路径时，构造不出来，否则可以构造出来。另外一个条件就是每个数出现次数为2次。

这个题我在做的时候，只想着去构造一个可行路径，因为这个题具有对称性质，但是我忽略掉的地方就是可行路径的查找不能只顺序遍历一次。

这个题还有一个做法就是用dfs去跑二分图染色。看到这个题解的时候，我恍然大悟啊，这不就是一个二分图的问题嘛。

并查集code：

#include<bits/stdc++.h>
using namespace std;
const int nn = 2*1e5+10;
int zufu[nn];
int cnt[nn];
int numcnt[nn];
int root(int a)
{
	int x = a,c;
	while(x!=zufu[x])
		x = zufu[x];
	while(zufu[a]!=x)
	{
		c = zufu[a];
		zufu[a] = x;
		a = c;
	}
	return x;
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		int n,x,y;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			zufu[i] = i,cnt[i]=numcnt[i]=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&x,&y);
			numcnt[x]++;numcnt[y]++;
			x=root(x);y=root(y);
			zufu[x] = y;
		}
		for(int i=1;i<=n;i++){
			cnt[root(i)]++;
		}
		int flag = 1;
		for(int i=1;i<=n;i++)
			if(cnt[i]&1||numcnt[i]!=2)
				flag = 0;
		if(flag) printf("YES\n"); else printf("NO\n");
	} 
}

二分图大佬code：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N],vec[N];
bool vis[N];
int col[N];
bool ok = true;
    
void dfs(int u){
    vis[u] = 1;
    for(auto v:g[u]){
        if(!vis[v]){/*如果尚未涂色，那就涂成与上一张牌不同的颜色，因为每条边连的是包含相同数字的牌*/
            col[v] = 1-col[u];
            dfs(v);
        }
        else if(col[v] == col[u]) ok = false;
    }
}

void solve() {
    int n;
    ok = true;
    cin>>n;
    for(int i = 1;i <= n;++i)g[i].clear(),vec[i].clear(),vis[i] = 0;
    for(int i = 1;i <= n;++i){
        int a,b;
        cin>>a>>b;
        vec[a].push_back(i);
        vec[b].push_back(i);/*记录每个数字在第几张牌上*/
        if(a==b) ok = false;/*同一张牌上的数字不同*/
    }
    for(int i = 1;i <= n;++i) if(vec[i].size()!=2) ok =false;/*每个数字出现的次数刚好为2*/
    if(!ok){
        cout<<"NO"<<endl;
        return;
    }
    for(int i = 1;i <= n;++i){
        int u = vec[i][0],v = vec[i][1];
        g[u].push_back(v);
        g[v].push_back(u);/*将包含相同数字的牌连起来*//*例如：{1,2}->{2,3}->{3,5}*/
    }
    for(int i = 1;i <= n;++i){
        if(!vis[i]){
            col[i] = 1;/*涂色*/
            dfs(i);
        }
    }
    if(ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
    
}
int tt;
signed main() {
    cin >> tt;
    while (tt--)solve();
}