Cod sursa(job #1511970)

Utilizator Emy1337Micu Emerson Emy1337 Data 27 octombrie 2015 14:49:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n,m,nrc;
const int MAX_N=100005;
vector < int > v[MAX_N];
int VIZ[MAX_N];

void DFS(int nod)
{


    VIZ[nod]=nrc;
    /*
    //1
    for(int i = 0; i < v[nod].size(); ++i){

         if(VIZ[v[nod][i]]==0)
             DFS(v[nod][i]);

    }
    //2
     vector < int > :: iterator it;
     for( it=v[nod].begin(); it!= v[nod].end(); ++it){

         if(VIZ[*it]==0)
             DFS(*it);

    }
    */
    //3
    for(auto it : v[nod])
    {

        if(VIZ[it]==0)
            DFS(it);
    }




}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(VIZ[i]==0)
        {
            nrc++;
            DFS(i);
        }
    }
    fout<<nrc;


    return 0;


}