Cod sursa(job #1073324)

Utilizator vyrtusRadu Criuleni vyrtus Data 5 ianuarie 2014 22:42:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

vector <int> drum[200001];
deque <int> coada;
int val[100001] = {0};
int n,m,k = 0;

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

void bfs(int start)
{
   coada.push_back(start);
    while (!coada.empty())
    {
        int nod = coada.front();
  for (int i=0; i<drum[nod].size(); ++i)
  {
      int t = drum[nod][i];
       if (val[t] == 0)
        {  val[t] = 1;
          coada.push_back(t);
       }
  }
coada.pop_front();

    }


}


int main()
{
      f >> n >> m;
      for (int i=0;i<m;i++)
      {
          int x,y;
          f >> x >> y;
          drum[x].push_back(y);
          drum[y].push_back(x);
      }

 for (int i=1;i<=n;i++)
 {
     if (val[i] == 0) { k++; bfs(i); };
 }

   g << k << endl;

    return 0;
}