Pagini recente » Cod sursa (job #91189) | Cod sursa (job #577582) | Cod sursa (job #2298968) | Cod sursa (job #277567) | Cod sursa (job #2805856)
#include <cstdio>
#include <deque>
using namespace std;
FILE* fin, * fout;
int start[100002], t[2][400002];
bool viz[100002];
deque <int>flu;
void ddfs(int nod)
{
flu.push_back(nod);
viz[nod] = 1;
while (!flu.empty()) {
nod = flu.front();
flu.pop_front();
int p;
p = start[nod];
while (p) {
if (viz[t[0][p]] == 0)
viz[t[0][p]] = 1, flu.push_back(t[0][p]);
p = t[1][p];
}
}
}
int main()
{
int n, m, x, y, k = 0;
fin = fopen("dfs.in", "r");
fout = fopen("dfs.out", "w");
fscanf(fin, "%d %d", &n, &m);
for (int i = 1;i <= m;++i) {
fscanf(fin, "%d %d", &x, &y);
t[0][++k] = y;
t[1][k] = start[x];
start[x] = k;
t[0][++k] = x;
t[1][k] = start[y];
start[y] = k;
}
int da = 0;
for (int i = 1;i <= n;++i)
if (viz[i] == 0) ++da, ddfs(i);
fprintf(fout, "%d", da);
return 0;
}