Cod sursa(job #1143085)

Utilizator tanduraDomnita Dan tandura Data 14 martie 2014 18:36:27
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int n,m,nr;
vector<int> x;
vector<queue<int> > q;

void citire()
{
    int a,b;

    ifstream f("dfs.in");

    f>>n>>m;

    x.resize(n+1);
    q.resize(n+1);

    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        q[a].push(b);
        q[b].push(a);
    }

    f.close();
}

void parcurgere(int v)
{
    int nod;
    while(!q[v].empty())
    {
        nod = q[v].front();
        q[v].pop();
        if(x[nod]==0)
        {
            x[nod]=nr;
            parcurgere(nod);
        }
    }
}

void rezolvare()
{
    for(int i=1;i<=n;i++)
        if(x[i]==0)
        {
            nr++;
            x[i]=nr;
            parcurgere(i);
        }
}

void afisare()
{
  ofstream g("dfs.out");
  g<<nr<<"\n";
  g.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}