Cod sursa(job #356635)

Utilizator xtremespeedzeal xtreme Data 15 octombrie 2009 18:01:55
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream.h>
#include <fstream.h>
#include <vector>
#define nmax 100005
using namespace std;

vector<int> G[nmax];
int N,M,mar[nmax],nrcc;


void citire()
     {freopen("dfs.in","r",stdin);
      int i,a,b;scanf("%d %d",&N,&M);
      for(i=1;i<=M;i++)
            {scanf("%d %d",&a,&b);G[a].push_back(b);G[b].push_back(a);}
      fclose(stdin);
      }
void DFS(int nod)
     {vector<int>::iterator it;
      for(it=G[nod].begin();it!=G[nod].end();it++)
                       if(!mar[nod])
                                DFS(*it);
      }
void rezolva()
     {int i;
      for(i=1;i<=N;i++)
           if(!mar[i])   {nrcc++;DFS(i);}
      }
void scrie()
     {freopen("dfs.out","w",stdout);
      printf("%d",nrcc);
      fclose(stdout);
      }
int main()
    {citire();
     rezolva();
     scrie();
     return 0;
     }