Cod sursa(job #1461894)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 16 iulie 2015 16:19:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define nmax 100005
#define mmax 200005

struct node
{
	int info;
	node *next;
}*lista[nmax],*p;

int n,m,s[nmax];

void df(int);

int main()
{
	fstream in("dfs.in", ios::in);
	fstream out("dfs.out", ios::out);

	int k=0,i,j,sum=0;

	in>>n>>m;

	while(in>>i>>j)
	{
		p=new node;
		p->info=j;
		p->next=lista[i];
		lista[i]=p;
		p=new node;
		p->info=i;
		p->next=lista[j];
		lista[j]=p;
	}

	for(i=1;i<=n;i++)
		if(s[i] == 0)
		{
			df(i);
			sum++;
		}
	
	out<<sum;



        
    in.close();
    out.close();

	return 0;
}

void df(int nod)
{

	node *k;
	s[nod]= 1;
	k=lista[nod];

	while(k)
	{
		if(s[k->info] == 0)
			df(k->info);
		k= k->next;
	}

}