Cod sursa(job #1059351)

Utilizator vyrtusRadu Criuleni vyrtus Data 16 decembrie 2013 16:39:21
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

struct Drum
{
    unsigned int x,y;
};

static int parcurs[100001];
static Drum a[200000];
int n,m;

void parcurgere (int nod)
{
deque <int> coada;

coada.push_back (nod);
parcurs[nod] = 1;
while (!coada.empty())
{
    for (int i=0; i<m; i++)
    {
        if ((a[i].x == coada.front()) && (parcurs[a[i].y] == 0))
        {
           parcurs[a[i].y] = 1;
           coada.push_back (a[i].y);
        }

        if ((a[i].y == coada.front()) && (parcurs[a[i].x] == 0))
        {
           parcurs[a[i].x] = 1;
           coada.push_back (a[i].x);
        }
    }
    coada.pop_front();
}

}

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

      f >> n >> m;
      for (int i=0;i<m;i++)
        f >> a[i].x >> a[i].y;

    for (int i=1; i<=n;i++)
         parcurs[i] = 0;

    int k=0;


     for (int i=n;i>0;i--)
     {
         if (parcurs[i] == 0 ) { k++; parcurgere(i);            }
     }

   g << k << endl;

    return 0;
}