Pagini recente » Istoria paginii runda/selectie_emag_mediu_2016_runda3 | Cod sursa (job #2025983) | Cod sursa (job #2218973) | Cod sursa (job #2169096) | Cod sursa (job #651351)
Cod sursa(job #651351)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int main()
{
FILE * f = fopen("dfs.in", "r");
int n, m ;
fscanf(f, "%i%i", &n, &m);
vector<vector<int> > a(n);
vector<int> viz(n);
int i, q, w;
for (i = 0; i < n; i++)
{
viz[i] = 0;
}
for (i = 0; i < m; i++)
{
fscanf(f, "%i%i", &q, &w);
a[q-1].push_back(w-1);
a[w-1].push_back(q-1);
}
fclose(f);
queue<int> coada;
int conex = 0;
for (int k = 0; k < n; k++)
{
if (viz[k] == 0)
{
conex++;
viz[k] = 1;
coada.push(k);
while(!coada.empty())
{
int e = coada.front();
coada.pop();
int len = a[e].size();
for (i = 0; i < len; i++)
{
if (viz[a[e][i]] == 0)
{
coada.push(a[e][i]);
viz[a[e][i]] = viz[e] + 1;
}
}
}
}
}
f = fopen("dfs.out", "w");
fprintf(f,"%i", conex);
fclose(f);
return 0;
}