Cod sursa(job #574482)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 7 aprilie 2011 11:08:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<stack>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,a,b,c,minim,w,y;
struct nod
{ int nr;
  nod *urm;} *v[100005],*p;
char viz[100005];
stack<int> st;
int main()
{
	int i;
	f>>n>>m;
	for(i=0;i<m;++i)
		{ f>>a>>b;
		  p=new nod;
		  p->nr=b;
		  p->urm=v[a];
		  v[a]=p;
		  p=new nod;
		  p->nr=a;
		  p->urm=v[b];
		  v[b]=p;
		}
	minim=1;
	while(minim<=n)
		{ viz[minim]='1';
		  ++c;
		  st.push(minim);
		  while(!st.empty())
			  if(v[st.top()]) 
				   { y=st.top();
					 w=v[y]->nr;
				     viz[w]='1';
					 st.push(w);
					 v[y]=v[y]->urm;
				   }
				   else st.pop();
		  while(viz[minim]) ++minim;
		}
	g<<c<<'\n';
	f.close(); g.close();
	return 0;
}