Cod sursa(job #726097)

Utilizator DeepGreenBurcea Iulian-Catalin DeepGreen Data 26 martie 2012 23:56:56
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<iostream>
#include<fstream>
#include<stack>
using namespace std;
#define max 100005


struct lista{
	unsigned long int vec;
	lista *next;
};

ifstream f("dfs.in");
ofstream g("dfs.out");
stack <unsigned long int> stiva;   
unsigned long int m;
 
void citire(unsigned long int &n, lista *v[max]){
	f>>n>>m;
	for(unsigned long int i=1;i<=n;i++)
		v[i]=NULL;
	for(unsigned long int i=1;i<=m;i++){
		unsigned long int x,y;
		f>>x>>y;
		if(v[x]==NULL){
			v[x]=new lista;
			v[x]->vec=y;
			v[x]->next=NULL;
		}
		else{
			lista *p=new lista;
			p->vec=y;
			p->next=v[x];
			v[x]=p;
		}
	}
}

unsigned long int nevizitat(unsigned long int n,unsigned long int viz[max]){
	unsigned long int i=1;
	while(i<=n)
		if(viz[i]==0)
			return i;
		else
			i++;
	return 0;
}	

unsigned long int  componente_conexe(unsigned long int n,lista *v[max],unsigned long int viz[max]){
	unsigned long int nr=0;
	lista *p;
	while(unsigned long int k=nevizitat(n,viz)){
		//unsigned long int i=nevizitat(n,viz);
		p=v[k];
		stiva.push(k);
		viz[k]=1;
		while(p!=NULL){
			if(viz[p->vec]==0){
				stiva.push(p->vec);
				viz[p->vec]=1;
				p=v[p->vec];
			}
			else
				p=p->next;
			if(p==NULL&&!stiva.empty()){
				stiva.pop();
				if(!stiva.empty())
					p=v[stiva.top()];
				
			}
		}
		nr++;
	}
	return nr;
}
		

	
int main(){
	unsigned long int n,viz[max]={0};
	lista *v[max];
	citire(n,v);
	g<<componente_conexe(n,v,viz)<<endl;
}