Cod sursa(job #1697006)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 30 aprilie 2016 15:06:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define N 100010

using namespace std;

std::vector<int> muc[N];
int verif[N],grad[N];

void parg(int c){
   int i;

   for(i=0;i<grad[c];i++){
      if(verif[ muc[c][i] ]==0){
         verif[muc[c][i]]=1;
         parg(muc[c][i]);
      }

   }
}

int main(){
   int i,n,m;
   int x,y,nrcomp=0;

   freopen("dfs.in","r",stdin);
   freopen("dfs.out","w",stdout);

   scanf("%d%d",&n,&m);

   for(i=0;i<m;i++){
      scanf("%d%d",&x,&y);
      muc[x].push_back(y);
      muc[y].push_back(x);
      grad[x]++;
      grad[y]++;
   }
   for(i=1;i<=n;i++){
      if(verif[i]==0){
         verif[i]=1;
         parg(i);
         nrcomp++;
      }
   }
   printf("%d",nrcomp);
    return 0;
}