Cod sursa(job #507189)

Utilizator GodiesVlad Voicu Godies Data 5 decembrie 2010 15:47:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#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;
}