Cod sursa(job #1274154)

Utilizator ArkinyStoica Alex Arkiny Data 23 noiembrie 2014 14:04:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
using namespace std;

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

struct Node
{
	int data;
	Node *next;
}*V[100001];
int viz[100001],N,M,nr;

void add_to_list(int nr,int data)
{
	   Node *p=new Node;
	   p->data=data;
	   p->next=V[nr];
	   V[nr]=p;
}
void remove_first(int nr)
{
	if(V[nr])
	{
		Node *p=V[nr];
		V[nr]=p->next;
		delete p;
	}
}

void DFS(int t)
{
	viz[t]=1;
	while(V[t])
	{
		if(!viz[V[t]->data])
			DFS(V[t]->data);
		remove_first(t);
	}
}

int main()
{
	in>>N;
	in>>M;
	int j,k;
	for(int i=1;i<=M;i++)
	{
		in>>j>>k;
		add_to_list(j,k);
		add_to_list(k,j);
	}

  for(int i=1;i<=N;i++)
   {
	   if(!viz[i])
	   {
		   DFS(i);
		   nr++;
	   }
   }
	out<<nr;
	in.close();
	out.close();


	return 0;
}