Cod sursa(job #1395035)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 20 martie 2015 22:51:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

#include <vector>

#define LE 100666

vector<int> H[LE];
bool viz[LE];

void dfs(int nod)
{
   int N=H[nod].size();  ///cati vecini are nodul nod
   int i;
   viz[nod]=true;

   for(i=0;i<N;++i)  ///parcurg vecini   !!! <vectoru> incepe de la 0  si merge pana la N-1 ,nu de la 1 pana la N
   {
      int vecin=H[nod][i];

      if (viz[vecin]==false)
         dfs(vecin);
   }
}

int main()
{

    int n,m,i;

    f>>n>>m;

    for(i=1;i<=m;++i)
    {
       int xx,yy;
       f>>xx>>yy;

       H[xx].push_back(yy);
       H[yy].push_back(xx);
    }

    int result=0;

    for(i=1;i<=n;++i)
      if (viz[i]==false)
      {
         ++result;
         dfs(i);
      }

    g<<result<<'\n';


    return 0;
}