Cod sursa(job #2176486)

Utilizator liaamzaLiA Amza liaamza Data 17 martie 2018 15:36:12
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
//Amza_020_InfoArena_dfs
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
#define MAXN 100000
typedef queue<int> Coada;
typedef Coada Vecini[MAXN];
 ifstream fin("dfs.in", ios::in);
 ofstream fout("dfs.out", ios::out);
 int n, m;
 Vecini vecini;
 int componenta[MAXN];
void citire(void)
{
   fin>>n>>m;
   int i, x, y;
   for(i=0;i<m;i++)
   {
       fin>>x>>y;
       vecini[x].push(y);
       vecini[y].push(x);
   }
   fin.close();
}
void dfs(int nod, int cc)
{
    componenta[nod]=cc;
    while(!vecini[nod].empty())
    {
        int vecin=vecini[nod].front();
        vecini[nod].pop();
        if(!componenta[vecin]){
            dfs(vecin,cc);
        }
    }
}
int parcurg(void)
{
    int i, rez;
    for(rez=i=0;i<MAXN;i++)
    {
        if(!componenta[i])
        {
            dfs(i, ++rez);
        }
    }
    return rez;
}
void scriu(int nC)
{
    fout<<nC<<endl;
    fout.close();
}

int main()
{
    citire();
    int nrComponente=parcurg();
    scriu(nrComponente);
    return 0;
}