Cod sursa(job #633589)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 14 noiembrie 2011 03:32:14
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<vector>
#include<stack>

using namespace std;

FILE *f,*g;
vector<int> a[100001];
int viz[100001],n,m;

void DFS(int v)
{
	stack<int> s;
	int j,primul;
	bool k;
	s.push(v);
	viz[v]=1;
	while(s.empty()==0)	{
		primul=s.top();
		k=0;
		for(j=0;j<a[primul].size()&&k==0;j++)
			if(viz[a[primul][j]]==0)
				k=1;
		if(k==1)	{
			j--;
			s.push(a[primul][j]);
			viz[a[primul][j]]=1;
		}
		else
			s.pop();
	}
}

int main()
{
	int i,x,y,conexe=0;
	f=fopen("dfs.in","r");
	g=fopen("dfs.out","w");
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;i++)	{
		fscanf(f,"%d %d",&x,&y);
		a[x].push_back(y);
	}
	for(i=1;i<=n;i++)
		if(viz[i]==0)	{
			conexe++;
			DFS(i);
		}
	fprintf(g,"%d",conexe);
	fclose(f);
	fclose(g);
	return 0;
}