Cod sursa(job #2063404)

Utilizator herbertoHerbert Mohanu herberto Data 11 noiembrie 2017 11:20:08
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;
#define MAXN 100005

char seen[MAXN];
vector <int> g[MAXN];
void dfs(int node){
  seen[node]=1;
  for(int i=0; i<g[node].size(); i++)
    if(seen[g[node][i]]==0)
      dfs(g[node][i]);
}
int main(){
  FILE*fin=fopen("dfs.in", "r");
  FILE*fout=fopen("dfs.out", "w");
  int n, m, x, y, i;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++){
    fscanf(fin, "%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int cnt=0;
  for(i=1; i<=n; i++){
    if(seen[i]==0){
      dfs(i);
      cnt++;
    }
  }
  fprintf(fout, "%d", cnt);
  return 0;
}