Cod sursa(job #146412)

Utilizator blasterzMircea Dima blasterz Data 1 martie 2008 17:59:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
using namespace std;
#define maxn 100001

bool use[maxn];

struct nd{ int x; nd*n;};

nd *a[maxn];
int n,m;

inline void add(int p, int q)
{
	nd *t=new nd;
	t->x=q;
	t->n=a[p];
	a[p]=t;
}

void read()
{
	int p, q;
	ifstream f("dfs.in");
	f>>n>>m;
	while(m--)
	{
		f>>p>>q;
		add(p,q);
		add(q,p);
	}
}
	
inline void dfs(int n)
{
	if(use[n]) return ;
	use[n]=1;
	nd *i;
	for(i=a[n]; i; i=i->n)
		if(!use[i->x])
			dfs(i->x);
}


int main()
{
	read();
	int nr=0;
	for(int i=1;i<=n;++i)
		if(!use[i])
		{
			++nr;
			dfs(i);
		}
	
	ofstream g("dfs.out");
	g<<nr<<"\n";
//	printf("%d\n", nr);
return 0;
}