Cod sursa(job #543764)

Utilizator worstbyteelev gigel worstbyte Data 28 februarie 2011 16:14:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>

using namespace std;
#define NM	100001
ifstream in("dfs.in");
ofstream out("dfs.out");

int n,m,viz[NM],s[NM],cc;

struct nod{
	int nr;
	nod* next;
};

nod* l[NM], * u[NM];

void add(nod* &l,int x){
	nod* nn=new(nod);
	nn->nr=x;
	nn->next=l;
	l=nn;
}

void df(int start){
	int y;
	nod* nc=u[start];
	while(nc){
		viz[start]=cc;
		y=nc->nr;
		nc=nc->next;
		if(!viz[y])
			df(y);
		u[start]=nc;
	}
	
}

int main(){
	int i,x,y;
	in>>n>>m;
	for(i=0;i<m;++i){
		in>>x>>y;
		add(l[x],y);
		add(l[y],x);
	}
	for(i=1;i<=n;++i)
		u[i]=l[i];
	
	for(i=1;i<=n;++i)
		if(!viz[i]){
			cc++;
			viz[i]=cc;
			df(i);
		}

	out<<cc;
	return 0;
}