Cod sursa(job #874383)

Utilizator SilviussMezei Silviu Silviuss Data 8 februarie 2013 11:43:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
using namespace std;

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

struct muchie
{
	int x;
	muchie *leg;
};

bool u[100001];
muchie **v;

void f(int k,muchie *p)
{
	u[k]=1;
	if(v[k]!=NULL)
	{
		p=v[k];
		if(u[p->x]==0)
			f(p->x,p);
		while(p->leg!=NULL)
		{
			p=p->leg;
			if(u[p->x]==0)
				f(p->x,p);
		}
	}
}

int main()
{
	int n,m,s=0,i,y,z;
	fin>>n>>m;
	v = new muchie*[n+1];
	muchie *p;
	for(i=1;i<=n;i++)
		v[i]=NULL;
	for(i=0;i<m;i++)
	{
		fin>>y>>z;
		if(v[y]==NULL)
		{
			v[y] = new muchie;
			v[y]->x=z;
			v[y]->leg=NULL;
		}
		else
		{
			p=v[y];
			while(p->leg!=NULL)
				p=p->leg;
			v[0] = new muchie;
			p->leg=v[0];
			v[0]->x=z;
			v[0]->leg=NULL;
		}
		if(v[z]==NULL)
		{
			v[z] = new muchie;
			v[z]->x=y;
			v[z]->leg=NULL;
		}
		else
		{
			p=v[z];
			while(p->leg!=NULL)
				p=p->leg;
			v[0] = new muchie;
			p->leg=v[0];
			v[0]->x=y;
			v[0]->leg=NULL;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(u[i]==0)
		{
			s++;
			f(i,p);
		}
	}
	fout<<s;
}