Cod sursa(job #1383278)

Utilizator laurenttlaurentiu pavel laurentt Data 10 martie 2015 05:50:55
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define MAXN 100004

vector<int> adj[2 * MAXN];
vector<bool> visited(MAXN, false);

void bfs(int node) {
  visited[node] = true; 
  int v_size = adj[node].size();
  for(int i = 0; i < v_size; ++i) {
    if(visited[adj[node][i]] == false) {
      bfs(adj[node][i]);
    }
  }
}

int main() {
  ifstream fin("dfs.in");
  ofstream fout("dfs.out");
  
  int N,M; fin >> N >> M;
  for(int i = 0; i < N; ++i) {
    int node1, node2; fin >> node1 >> node2;
    adj[node1].push_back(node2);
    adj[node2].push_back(node1);
  }

  int components = 0;
  for(int i = 1; i <= N; ++i) {
    if(visited[i] == false) {
      ++components;
      bfs(i);
    }
  }
  fout << components << "\n";
  return 0;
}