Cod sursa(job #482516)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 3 septembrie 2010 19:32:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
vector<bool> passed;

int DFS(vector<vector<int> >& graph, int start)
{
	if(passed[start])
		return 0;
	stack<int> st;
	st.push(start);
	while(!st.empty())
	{
		int node=st.top();
		st.pop();
		passed[node]=true;
		//cout<<node<<" ";
		for(unsigned int i=0; i<graph[node].size(); ++i)
		{
			if(!passed[graph[node][i]])
				st.push(graph[node][i]);
		}
	}
	//cout<<endl;
	return 1;
}

int ConexComponents(vector<vector<int> >& graph, int n)
{
	int comp=0;
	for(int i=1; i<=n; ++i)
	{
		comp+=DFS(graph,i);
	}
	return comp;
}

int main()
{
	int n,m,x,y;
	fstream fin("dfs.in", fstream::in);
	fstream fout("dfs.out", fstream::out);
	vector<vector<int> >graph;
	
	fin>>n>>m;
	graph.resize(n+2);
	passed.resize(n+2);
	for(int i=0; i<m; ++i)
	{
		fin>>x>>y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	
	fout<<ConexComponents(graph, n)<<endl;
	
	fin.close();
	fout.close();
	return 0;
}