Cod sursa(job #1667465)

Utilizator dyana_valeryaDiana-Valeria dyana_valerya Data 28 martie 2016 22:28:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#define e endl

using namespace std;
					ifstream f("dfs.in");
					ofstream t("dfs.out");
char sp[]="   ";

typedef struct cel
					{
						int info;
						cel *next;
					}*nodic;
					
															bool viz[1000007];
															int m,n,x,y,conex;
															nodic lda[1000007];
	void add(int x,nodic &y)
	{
		nodic r=new cel;
		r->info=x;
		r->next=y;
		y=r;
	}
	
void dfs(int x)
	{
		if(!viz[x]){
			viz[x]=1; 
			for(nodic p=lda[x];p;p=p->next)  dfs(p->info);
		}
	}
	
int main(){
	f>>n>>m;
	while(m--){
		f>>x>>y;
		add(x,lda[y]);
		add(y,lda[x]); 
	}
	
	for(int i=1;i<=n;++i) 
		if(!(viz[i]))
		dfs(i) , conex++;
		
		t<<conex<<e;
	return 0;
}