F图与G图

标签： const int merge ans using find

https://codeforces.com/problemset/problem/2060/E
https://blog.csdn.net/MenghuanL/article/details/145268191?ops_request_misc=&request_id=&biz_id=102&utm_term=codeforces%20998&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-1-145268191.142^v101pc_search_result_base2&spm=1018.2226.3001.4187

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N =2e5+10;
const int mod = 1e9 + 7;
int f[N*2];
int find(int x){
	if(f[x]==x) return f[x];
	else return f[x]=find(f[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(f[fx]!=f[fy]){
		f[fx]=fy;
	}
}
void solve(){
	int n,m1,m2;cin>>n>>m1>>m2;
	for(int i=1;i<=2*n;i++){
		f[i]=i;
	}
	vector<pii> v1,v2;
	for(int i=1;i<=m1;i++)
	{
		int u,v;cin>>u>>v;
		v1.push_back({u,v});
	}
	for(int i=1;i<=m2;i++){
		int u,v;cin>>u>>v;
		v2.push_back({n+u,n+v});
		merge(n+u,n+v);
	}
	int ans=0;
	for(auto [u,v]:v1){
		if(find(u+n)==find(v+n)){
			merge(u,v);
		}
		else ans++;
	}
	for(auto [u,v]:v2){
		if(find(u-n)!=find(v-n)){
				ans++;
				merge(u-n,v-n);
		}
			
	}
	cout<<ans<<endl;
}
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}

注意是u和v之间有路径即可

标签：,const,int,merge,ans,using,find
From： https://www.cnblogs.com/laileou/p/18686438