Mai intai trebuie sa te autentifici.

Cod sursa(job #629915)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 4 noiembrie 2011 10:24:26
Problema Parcurgere DFS - componente conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int N=300010;

struct comp{
	int nod,nrvec;
}stack[N];

vector <int> muchie[N];
int n,m,compcon,stacksize;
bool viz[N];

void citire(){
	int i,x,y;
	in>>n>>m;
	for(i=1;i<=n;++i){
		in>>x>>y;
		muchie[x].push_back(y);
		muchie[y].push_back(x);
	}
}

void DFS(int x){
	int i,nod,ok;
	nod=x;
	stacksize++;
	stack[stacksize].nod=x;
	stack[stacksize].nrvec=0;
	while(stacksize!=0){
		nod=stack[stacksize].nod;
		viz[nod]=true;
		ok=0;
		for(i=stack[stacksize].nrvec;i<muchie[nod].size();++i){
			if(!viz[muchie[nod][i]]){
				stacksize++;
				stack[stacksize].nod=muchie[nod][i];
				stack[stacksize].nrvec=0;
				ok=1;
				break;
			}
		}
		if(!ok){
			stacksize--;
		}
	}
}

void rezolvare(){
	int i;
	for(i=1;i<=n;++i){
		if(!viz[i]){
			compcon++;
			DFS(i);
		}
	}
}

int main(){
	citire();
	rezolvare();
	out<<compcon;
	return 0;
}