Cod sursa(job #1383279)

Utilizator laurenttlaurentiu pavel laurentt Data 10 martie 2015 06:03:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 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 dfs(int node) {
  //  cout << node << " ";
  visited[node] = true; 
  int v_size = adj[node].size();
  for(int i = 0; i < v_size; ++i) {
    if(visited[adj[node][i]] == false) {
      dfs(adj[node][i]);
    }
  }
}

int main() {
  ifstream fin("dfs.in");
  ofstream fout("dfs.out");
  
  int N,M; fin >> N >> M;
  for(int i = 0; i < M; ++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) {
      //      cout << i << " -> ";
      ++components;
      dfs(i);
      //      cout << "\n";
    }
  }
  fout << components << "\n";
  return 0;
}