Cod sursa(job #677555)

Utilizator legendarulDavid Anton Erculescu legendarul Data 10 februarie 2012 12:32:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;

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

int m,n,viz[1000001],cc=1;
struct nod{
					 int info;
					 nod *next;
					};
nod* la[100001];

void add(int x,int y)
{ nod *n=new nod;
	n->info=y;
	n->next=la[x];
	la[x]=n;
	n=new nod;
	n->info=x;
	n->next=la[y];
	la[y]=n;
}

void citire()
{ in>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{ in>>x>>y;
		add(x,y);
	}
}

void df(int s)
{ viz[s]=1;
	nod *nc=la[s];
	while(nc)
	{	int y=nc->info;
		if(!viz[y])
		{ df(y);
		}
		nc=nc->next;
	}
}

int main()
{ citire();
	int i,c=0;
	for(i=1;i<=n;i++)
	{ if(!viz[i])
		{ c++;
			df(i);
		}
	}
	out<<c;
	return 0;
}