Cod sursa(job #855138)

Utilizator taigi100Cazacu Robert taigi100 Data 14 ianuarie 2013 18:16:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <string.h>
#include <vector>
#include <list>
#include <stdio.h>

#define Nmax 100005

std::list<int> stack;
std::vector<int> nodes[Nmax];
int n,m;
int vis[Nmax];

void DFS(int Start)
{
	stack.push_back(Start);
	while(!stack.empty())
	{
		int i;
		int top=stack.back();
		if(!vis[top])
		{
		vis[top]=1;
		}
		for(i=0;i< nodes[top].size(); i++)
		{
			if(!vis[nodes[top][i]])
			{
				stack.push_back(nodes[top][i]);
				i=nodes[top].size()+2;
			}
		}
		if(i==nodes[top].size())
		{
             stack.pop_back();
		}
	}
}

int main()
{
	FILE *f=fopen("dfs.in","r");
	fscanf(f,"%d %d",&n,&m);
	int a,b;
	
	for(int i=0;i<m;i++)
	{
		fscanf(f,"%d %d",&a,&b);
		nodes[a].push_back(b);
		nodes[b].push_back(a);
	}
	int nrc=0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
	       DFS(i);
		   nrc++;
		}
	}
	FILE *g=fopen("dfs.out","w");
	fprintf(g,"%d",nrc);
	return 0;

}