Cod sursa(job #1629863)

Utilizator AnaMariaPintilieAna Maria Pintilie AnaMariaPintilie Data 4 martie 2016 19:29:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 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;
	visited[vertex]=true;
    for(int i = 0;i<graph[vertex].size();i++)
        if(!visited[graph[vertex][i]])
                dfs(graph[vertex][i]);
}


int main()
{
    int x,y,i,k=0;
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	fin>>N>>M;
	graph.resize(N);
	visited.resize(N,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;
}