Cod sursa(job #720614)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 22 martie 2012 19:44:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>

using namespace std;

const int knmax = 100005;

int verts, edges, sol, vis[knmax];
vector<int> graph[knmax];

void read(){
  assert(freopen("dfs.in", "r", stdin) != NULL);

  scanf("%d%d", &verts, &edges);

  int i, aux_x, aux_y;
  for(i = 1; i <= edges; ++i){
    scanf("%d%d", &aux_x, &aux_y);

    graph[aux_x].push_back(aux_y);
    graph[aux_y].push_back(aux_x);
  }

}

void dfs(int x){
  vis[x] = 1;

  vector<int>::iterator it;
  for(it = graph[x].begin(); it < graph[x].end(); ++it)
    if(!vis[*it])
      dfs(*it);
}

void solve(){
  for(int i = 1; i <= verts; ++i)
    if(!vis[i]){
      dfs(i);

      ++sol;
    }

}

void write(){
  assert(freopen("dfs.out", "w", stdout) != NULL);

  printf("%d", sol);
}

int main(){
  read();
  solve();
  write();
  return 0;
}