Official
D - Unicyclic Components Editorial by en_translator
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;
}
posted:
last update: