Pagini recente » Cod sursa (job #1415168) | Cod sursa (job #76693) | Cod sursa (job #1175420) | Cod sursa (job #2726525) | Cod sursa (job #641630)
Cod sursa(job #641630)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int main()
{
FILE * f = fopen("dfs.in", "r");
int n, m, s;
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;
}
//viz[s-1] = 1;
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;
}