Cod sursa(job #542007)

Utilizator alex@ndraAlexandra alex@ndra Data 25 februarie 2011 17:53:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
//PARCURGERE IN ADANCIME

#include<fstream>
#include<vector.h>
using namespace std;
#define Nmax 100001

vector<int> G[Nmax];
int vizitat[Nmax], n, m;

void citire()
{int i, x, y;
     ifstream f("dfs.in");
        f>>n>>m;
        
     for(i=1;i<=m;i++)
        {
          f>>x>>y;
          G[x].push_back(y);
          G[y].push_back(x);
        }
        
     f.close();
 }
 
void dfs(int nod)
{
     int i, vecini;
     vecini=G[nod].size();
     vizitat[nod]=1;
     
     for(i=0;i<vecini;i++)
        if(!vizitat[G[nod][i]])
           dfs(G[nod][i]);
           
 }
 
int main()
{
    int i,nr=0; 
    citire();
    
    for(i=1;i<=n;i++)
      if(!vizitat[i])
         {  
            nr++;
            dfs(i);
         }
    
    ofstream g("dfs.out");
       g<<nr;
    g.close();
    
    return 0;
}