Cod sursa(job #1799302)

Utilizator msciSergiu Marin msci Data 6 noiembrie 2016 01:32:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>
using namespace std;

int N, M, ans;

struct Node {
  vector<int> adj;
  bool visited;
  int comp;
};

Node V[100005];

void dfs(int i, int c) {
  if (V[i].visited) return;
  V[i].visited = true;
  V[i].comp = c;
  for (int j = 0; j < V[i].adj.size(); j++) {
    dfs(V[i].adj[j], c);
  }
}

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

  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    V[a].adj.push_back(b);
    V[b].adj.push_back(a);
  }

  for (int i = 1; i <= N; i++) {
    if (!V[i].visited) dfs(i, ans++);
  }
  cout << ans << endl;
}