Cod sursa(job #2449661)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 20 august 2019 13:41:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>

using namespace std;

const int N = 100001;
int n, m, s;
int t[N];

int par(int a) {
  if (t[a] == a)
    return a;
  else
    return t[a] = par(t[a]);
}

int main() {
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);

  scanf("%d %d", &n, &m);
  s = n;
  for (int i = 1; i <= n; i++)
    t[i] = i;
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a = par(a);
    b = par(b);
    if (a != b) {
      s--;
      t[a] = b;
    }
  }

  printf("%d\n", s);

  return 0;
}