Cod sursa(job #726452)

Utilizator DeepGreenBurcea Iulian-Catalin DeepGreen Data 27 martie 2012 11:20:53
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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,viz[max]={0},k;
lista *v[max];
 
void citire(unsigned long int &n){
	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 i=k+1;
	while(i<=n)
		if(viz[i]==0)
			return i;
		else
			i++;
	return 0;
}	

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

	
int main(){
	unsigned long int n;
	
	citire(n);
	g<<componente_conexe(n)<<endl;
}