Cod sursa(job #543978)

Utilizator MacaMacarescu Alexandru Maca Data 28 februarie 2011 21:06:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod
{	vector<int>vecin;
};
int N,M,nr;
stack<int>st;
nod graf[100001];
bool vizitat[100001];
void dfs(int x)
{	int i;
	vizitat[x]=1;
	st.push(x);
	while(!st.empty())
	{	x=st.top(); st.pop();
		for(i=0;i<graf[x].vecin.size();i++)
			if(vizitat[graf[x].vecin[i]]==false)
				vizitat[graf[x].vecin[i]]=true , st.push(graf[x].vecin[i]);
	}
}	
int main()
{	int i,x,y;
	in>>N>>M;
	for(i=1;i<=M;i++)
	{	in>>x>>y;
		graf[x].vecin.push_back(y);
		graf[y].vecin.push_back(x);
	}
	for(i=1;i<=N;i++)
		if(vizitat[i]==false)
			dfs(i) , nr++;
	out<<nr;
	in.close();
	out.close();
	return 0;
}