One can manage the connectivity of an undirected graph easily with a data structure called Union-Find or DSU (Disjoint Set Union). In this editorial, we describe a solution that uses dsu of AtCoder Library.

In order to solve this problem, we have to determine which connected component each vertex belongs to. AtCoder Library dsu enables us to find the index of representative vertex of the connected component that vertex \(x\) belongs to, as follows:

// Use atcoder::dsu D to assign to l the index of the representative vertex of the connected component containing x
l = D.leader(x);

It is sufficient to check if every connected component has the same number of edges and vertices.

Sample code (C++)

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

int main() {
    
	int N,M;
	cin>>N>>M;
	vector<int> u(M),v(M);
	for(int i=0;i<M;i++){
		cin>>u[i]>>v[i];
		u[i]--,v[i]--;
	}
	
	dsu D(N);
	for(int i=0;i<M;i++){
		D.merge(u[i],v[i]);
	}
	
	vector<int> vs(N),es(N);
	for(int i=0;i<N;i++){
		vs[D.leader(i)]++;
	}
	
	for(int i=0;i<M;i++){
		es[D.leader(u[i])]++;
	}
	
	if(vs==es)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}