Cod sursa(job #2325035)

Utilizator Lazea_Iosua_UVT_FMILazea Iosua Lazea_Iosua_UVT_FMI Data 21 ianuarie 2019 21:24:53
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream.h>
ifstream f("dfs.in");
ofstream g("dfs.out");
#define Nmax 100100
long n, m, nr, viz[Nmax];
struct lista
{
	long inf;
	lista *urm;
}*a[Nmax];
void add(long x, long y)
{
	lista * q = new lista;
	q->inf = y;
	q->urm = a[x];
	a[x] = q;
}
void read()
{
 long x, y;
	f >> n >> m;
	for(long i = 1; i <= m; i++)
	{
		f >> x >> y;
		add(x, y);
		add(y, x);
	}
}
void alg(int x)
{
	lista *c = new lista;
	c->inf = x;
	c->urm = NULL;
	lista *u = c;
	while(c)
	{
		for(lista *q = a[c->inf]; q; q = q->urm)
		{
			if(viz[q->inf] == 0)
			{
				lista *p = new lista;
				p->inf = q->inf;
				p->urm = NULL;
				u->urm = p;
				u = p;
				viz[q->inf] = 1;
			}
		}
		c = c->urm;
	}
}
int main()
{
	read();
	for(long i = 1; i <= n; i++)
		if(viz[i] == 0)
		{
			alg(i);
			nr++;
		}
	g << nr << endl;
 f.close();
 g.close();
 return 0;
}