Cod sursa(job #290217)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 27 martie 2009 17:24:03
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
struct nod {int inf;nod *next;} *a[100010],*p;
stack<int> st;
int n,m,i,ut[100010],nr,x,y;
void add(nod *&v,int y)
{
	nod *c=new nod;
	c->inf=y;
	c->next=v;
	v=c;
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(a[x],y);
		add(a[y],x);
	}
	for(i=1;i<=n;i++)
		if(!ut[i])
		{
			nr++;
			st.push(i);
			while(!st.empty())
			{
				for(p=a[st.top()];p;p=a[p->inf]->next)
					if(!ut[p->inf])
						st.push(p->inf);
				if(!ut[st.top()])
					ut[st.top()]=1;
				else
					st.pop();
			}
		}
	printf("%d\n",nr);
	return 0;
}