無向グラフの連結性を簡潔に管理する方法として、UnionFind(DSU)というデータ構造があります。本解説ではAtCoder Libraryのdsuを用いた解法を示します。

本問を解く上で、与えられたグラフにおいて各頂点・各辺がどの連結成分に含まれているかを把握する必要があります。AtCoder Libraryのdsuでは、以下のようにして頂点 \(x\) が含まれる連結成分を代表する頂点の番号を得られます。

//atcoder::dsu Dを使い、lにxが含まれる連結成分を代表する頂点の番号を代入する
l = D.leader(x);

これを用いて任意の連結成分において頂点数と辺数が等しいかどうかを判定すれば良いです。

実装例(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;
}