Pagini recente » Cod sursa (job #1811902) | tema | Istoria paginii runda/lol_asd/clasament | tema | Cod sursa (job #2176486)
//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;
}