Pagini recente » Istoria paginii utilizator/costinj | Statistici Vlad Matei Draghici (draghici.vlad18) | Cod sursa (job #440140) | Profil Angel | Cod sursa (job #2176502)
//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;
}