Cod sursa(job #1629855)

Utilizator AnaMariaPintilieAna Maria Pintilie AnaMariaPintilie Data 4 martie 2016 19:21:49
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int M,N;
vector <vector <int> > graph;
vector <bool> visited;

void dfs(int vertex)
{
	if(vertex<0 || vertex>N-1) return;

	stack <int> s;
	int element,i;
	bool found;

	s.push(vertex);
	visited[vertex]=true;
	while (!s.empty())
	{
		element=s.top();
		found=false;
		for(i = 0;i<graph[element].size() && !found;i++)
            if(!visited[graph[element][i]]) found=true;
        if(found)
        {
            i--;
            s.push(graph[element][i]);
            visited[graph[element][i]]=true;
        }
        else s.pop();

	}

}


int main()
{
    int x,y,i,k=0;
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	fin>>N>>M;
	graph.resize(N);
	visited.resize(M,false);

	for(i=0;i<M;i++)
    {
        fin>>x>>y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    fin.close();

    for(i=0;i<visited.size();i++)
        if(!visited[i])
            {dfs(i);k++;}

    fout<<k;
    fout.close();
	return 0;
}