Cod sursa(job #854270)

Utilizator ioanapopaPopa Ioana ioanapopa Data 13 ianuarie 2013 02:15:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<algorithm>
//#include<iostream>
using namespace std;

int N, M, use[100001];

struct lista
{
	int nod;
	lista *urm;
};
	lista *G[100001];
	
	void add ( int i, int j )
{
	lista *p = new lista;
	p->nod = j;
	p->urm = G[i];
	G[i] = p;
}

void inPut()
{
	int i, j;

	scanf ( "%d %d", &N, &M );

	while ( M-- )
	{
		scanf ( "%d %d", &i, &j );
		add (i, j);
		add (j, i);
	}
	
	}
	void depth(int nd)
	{
	lista *p;
	use[nd] = 1;
	for(p=G[nd]; p!=NULL; p=p->urm)
	if(!use[p->nod])
	depth(p->nod);
	}
	int main()
	{
		freopen ( "dfs.in", "r", stdin ) ;
		inPut();
		int Nr=0;
		for(int i=1; i<=N; i++)
		if(!use[i])
	{
		++Nr;
		depth(i);
	}
		freopen ( "dfs.out", "w", stdout );
		printf ( "%d\n", Nr );
		fclose(stdout);
	return 0;
}