Pagini recente » Cod sursa (job #270206) | Cod sursa (job #1364390) | Cod sursa (job #2452562) | Cod sursa (job #1704797) | Cod sursa (job #507189)
Cod sursa(job #507189)
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <vector>
#define maxn 100000
using namespace std;
vector<int> *v = new vector <int> [maxn];
stack<int> vi;
int visited[maxn];
int main()
{
unsigned int i, n, m, x, y, count = 0;
FILE *f = fopen("dfs.in", "rt");
FILE *g = fopen("dfs.out", "wt");
fscanf(f, "%d%d" , &n, &m);
for (i = 0; i < m; i++) {
fscanf(f, "%d%d" , &x, &y);
v[--x].push_back(--y);
v[y].push_back(x);
}
for (i = 0; i < n; i++) {
visited[i] = 0;
}
for (i = 0; i < n; i++) {
if (visited[i] != 1) {
count++;
vi.push(i);
while(!vi.empty()) {
x = vi.top();
vi.pop();
visited[x] = 1;
for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); it++) {
if(visited[*it]!=1) {
vi.push(*it);
}
}
}
}
}
fprintf (g, "%d" , count);
fclose(f);
fclose(g);
return 0;
}