Cod sursa(job #696411)

Utilizator Ast09Stoica Anca Ast09 Data 28 februarie 2012 18:27:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#include<stack>
using namespace std;

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

int n,m,y,w,a,b,c,i,minim,nr,viz[100005];
struct nod
{
	int x;
	nod *next;
}	*v[100005],*p;
stack<int> q;

int main()
{
	f>>n>>m;
	
	for(i=1;i<=m;i++)
	{
		f>>a>>b;
		p=new nod;
		p->x=b;
		p->next=v[a];
		v[a]=p;
		
		p=new nod;
		p->x=a;
		p->next=v[b];
		v[b]=p;
		
	}
	
	minim=1;
	
	while(minim<=n)
	{
		viz[minim]=1;
		nr++;
		q.push(minim);
		
		while(!q.empty())
		{
			if(v[q.top()])
			{
				y=q.top();
				w=v[y]->x;
				viz[w]=1;
				q.push(w);
				v[y]=v[y]->next;
			}
			else q.pop();
		}
		while(viz[minim]) minim++;
	}
	
	g<<nr<<'\n';
	
	f.close();
	g.close();
	return 0;
}