Cod sursa(job #1142933)

Utilizator tanduraDomnita Dan tandura Data 14 martie 2014 14:00:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

int n,m,nr;
int marc[100001];
queue<int> q[100001];

void citire()
{
    int a,b;

    ifstream f("dfs.in");

    f>>n>>m;

    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(marc[nod]==0)
        {
            marc[nod]=nr;
            parcurgere(nod);
        }
    }
}

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

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

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