Cod sursa(job #1657703)

Utilizator pickleVictor Andrei pickle Data 20 martie 2016 18:27:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 100555;

int N, M, a, b;
vector<int> G[Nmax];
char vis[Nmax];

void dfs(int x) {
  vis[x] = 1;
  for(int y: G[x])
    if (!vis[y])
      dfs(y);
}

int main() {
  fin >> N >> M;
  while(M--) {
    fin >> a >> b;
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int ans = 0;
  for(int i = 0; i < N; ++i)
    if (!vis[i])
      ++ans, dfs(i);

  fout << ans << endl;

  return 0;
}