Cod sursa(job #1044935)

Utilizator rvnzphrvnzph rvnzph Data 30 noiembrie 2013 17:13:40
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
//info:	stack-iterative

#include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <cstring>

using namespace std;

vector <int> g[100001];
stack <int> st;
int use[100001];

void dfs(int start)
{
	st.push(start);
	while(!st.empty())
	{
		int node=st.top();
		st.pop();

		if(use[node]) continue;
		use[node]=1;

		for(vector<int>::iterator it=g[node].begin();it!=g[node].end();++it)
			if(!use[*it]) st.push(*it);
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	int M,N,x,y;
	scanf("%d%d",&N,&M);
	while(M--)
	{
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	memset(use,0,sizeof(use));
	int cnt=0;

	for(int i=1;i<=N;++i)
		if(!use[i]) dfs(i), ++cnt;

	printf("%d\n",cnt);

	return 0;
}