Cod sursa(job #2176502)

Utilizator liaamzaLiA Amza liaamza Data 17 martie 2018 16:05:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//Amza_020_InfoArena_dfs
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
#define MAXN 100000
vector<int> vecini[MAXN+1];
 ifstream fin("dfs.in", ios::in);
 ofstream fout("dfs.out", ios::out);
 int n, m, nrComponente;
 int componenta[MAXN+1];
void citire(void)
{
   fin>>n>>m;
   int i, x, y;
   for(i=0;i<m;i++)
   {
       fin>>x>>y;
       vecini[x].push_back(y);
       vecini[y].push_back(x);
   }
   fin.close();
}
void dfs(int nod)
{
    componenta[nod]=nrComponente;
    for (std::vector<int>::iterator it = vecini[nod].begin() ; it != vecini[nod].end(); ++it)
    {
        int vecin=*it;
        if(!componenta[vecin]){
            dfs(vecin);
        }
    }
}
void parcurg(void)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(!componenta[i])
        {
            ++nrComponente;
            dfs(i);
        }
    }
}
void scriu(int nC)
{
    fout<<nC<<endl;
    fout.close();
}

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