Cod sursa(job #1422869)

Utilizator andreiagAndrei Galusca andreiag Data 20 aprilie 2015 04:03:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
const int Nmax = 100555;

int par[Nmax];
int hgt[Nmax];

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

void join(int a, int b) {
  a = root(a);
  b = root(b);
  if (a == b)
    return;
  if (hgt[a] > hgt[b])
    par[b] = a;
  else
    par[a] = b;

  if (hgt[a] == hgt[b])
    hgt[b]++;
}

int main()
{
  ifstream f ("dfs.in");
  ofstream g ("dfs.out");
  
  int N, M, a, b;
  f >> N >> M;
  for (int i = 1; i <= N; i++)
    par[i] = i;
  while (M--) {
    f >> a >> b;
    join(a, b);
  }
  int ans = 0;
  for (int i = 1; i <= N; i++)
    ans += (par[i] == i);
  
  g << ans << '\n';

  return 0;
}