Cod sursa(job #1996761)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 2 iulie 2017 15:57:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fi ("dfs.in");
ofstream fo ("dfs.out");
vector <int> v[100004],stiva;
int nrnod,nrmuchii,i,nod1,nod2,pnod,nod,sol,nextnod;
bool marcat[100005];
int main()
{
    fi>>nrnod>>nrmuchii;
    for (i=1;i<=nrmuchii;i++)
    {
      fi>>nod1>>nod2;
      v[nod1].push_back(nod2);
      v[nod2].push_back(nod1);
    }
    for (pnod=1;pnod<=nrnod;pnod++)
      if (!marcat[pnod])
    {
      marcat[pnod]=true;
      sol++;
      stiva.push_back(pnod);
      while (!stiva.empty())
      {
        nod=stiva.back();
        stiva.pop_back();
        for (i=0;i<v[nod].size();i++)
        {
          nextnod=v[nod][i];
          if (!marcat[nextnod])
          {
            marcat[nextnod]=true;
            stiva.push_back(nextnod);
          }
        }
      }
    }
    fo<<sol;
    return 0;
}