Cod sursa(job #1098390)

Utilizator horatiu13Horatiu horatiu13 Data 4 februarie 2014 19:44:13
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#define Nmax 100002
#define Mmax 2*Nmax
using namespace std;

struct nod
{
	int x;
	nod *urm;
}*G[Nmax];

FILE *fi = fopen("dfs.in", "r");
FILE *fo = fopen("dfs.out", "w");
int viz[Nmax];
int nrc = 0;
int n;
int m;

void adauga(int x, int y)
{
	nod *q = new nod;
	q->x = y;
	q->urm = 0;
	
	if (!G[x])
	{
		G[x] = q;
	}
	else if (G[x]->x > y)
	{
		q->urm = G[x];
		G[x] = q;
	}
	else
	{
		nod *p;
		nod *r;
		for (p = G[x]; p && p->x < y; r=p, p=p->urm);
		
		r->urm = q;
		if (p) r->urm = q;
	}
}

void citire()
{
	int x, y;
	
	fscanf(fi, "%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		fscanf(fi, "%d%d", &x, &y);
		adauga(x, y);
		adauga(y, x);
	}
}

void DF(int x)
{
	viz[x] = 1;
	for (nod *p=G[x]; p; p=p->urm)
		if (!viz[p->x])
			DF(p->x);
}

int main()
{
	citire();
	for (int i=1; i<=n; i++)
		if (!viz[i])
		{
			++nrc;
			DF(i);
		}
	fprintf(fo, "%d", nrc);	
	return 0;
}