Submission #8893462

---

Source Code Expand

//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=acos(-1);
const int inf=1e9;
const ll INF=1e18;
int n,m,par[100005]={},a,b;
int find(int x) {
  if(par[x]==x) {
    return x;
  }
  return par[x]=find(par[x]);
}
bool same(int x,int y) {
  return find(x)==find(y);
}
void unit(int x,int y) {
  x=find(x);
  y=find(y);
  if(x!=y) {
    par[x]=y;
  }
}
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    par[i]=i;
  }
  for(int i=0; i<m; i++) {
    cin >> a >> b;
    a--,b--;
    if(!same(a,b)) {
      n--;
      unit(a,b);
    }
  }
  cout << n-1 << endl;
}

Submission Info

Judge Result