Cod sursa(job #468513)

Utilizator andunhillMacarescu Sebastian andunhill Data 3 iulie 2010 22:39:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>
#include<stack>
#include<vector>
#include<bitset>
using namespace std;
#define nm 100001
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,x,y,sol;
vector<int>map[nm];
bitset<nm>v;
stack<int>st;
vector<int>::iterator it;
void dfs(int i)
{	v[i]=1 , st.push(i);
	while(!st.empty())
	{	i=st.top(); st.pop();
		for(it=map[i].begin();it!=map[i].end();it++)
			if(v[*it]==0) v[*it]=1,st.push(*it);
	}
}
int main()
{	f>>N>>M;
	for(int i=1;i<=M;i++)
	{	f>>x>>y;
		map[x].push_back(y) , map[y].push_back(x);
	}
	for(int i=1;i<=N;i++)
	{	if(v[i]==0) dfs(i) , sol++;
	}
	g<<sol;
	f.close();
	g.close();
	return 0;
}