Cod sursa(job #476244)

Utilizator andrey932Andrei andrey932 Data 10 august 2010 13:03:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <stdio.h>
#include <slist.h>
#include <bitset>
#include <stack>
using namespace std;
#define MAXN 100003

FILE *fin=fopen("dfs.in","r"),*fout=fopen("dfs.out","w");
slist<int> vecini[MAXN];
bitset<MAXN> viz;
stack<int> s;
int n,m,i,a,b,tot,c;

void dfs(int a) {
	s.push(a);
	while (!s.empty()) {
		c=s.top(); s.pop();
		viz[c]=1;
		while (!vecini[c].empty()) {
			s.push(vecini[c].front());
			vecini[c].pop_front();
		}
	}	
}


int main()
{
	fscanf(fin,"%d %d\n",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(fin,"%d %d\n",&a,&b);
		vecini[a].push_front(b);
		vecini[b].push_front(a);
	}
	tot=0;
	for(i=1;i<=n;i++) {
		if (!viz[i]) {
			tot++;
			dfs(i);
		}
	}
	fprintf(fout,"%i\n",tot);
	fclose(fout);	
	return 0;
}