Cod sursa(job #1705467)

Utilizator alex95panPandelea Alexandru alex95pan Data 20 mai 2016 17:22:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

vector<int> g[100001];
int visit[100001];
int comp_conex;

void dfs(int ind)
{
	visit[ind] = 1;
	for (unsigned int i = 0; i < g[ind].size(); i++)
	{
		int ind_fiu = g[ind][i];
		if (visit[ind_fiu] == 0)
		{
			visit[ind_fiu] = 1;
			dfs(ind_fiu);
		}
	}
}

/* Aplica dfs pana se viziteaza toate nodurlie */
void solve(int n)
{

	for (int i = 1; i <= n; i++)
		if (visit[i] == 0)
		{
		    comp_conex++;
			dfs(i);
		}
}

int main()
{
    int n,m;
    fstream f, out;
	f.open("dfs.in", ios::in);
	out.open("dfs.out", ios::out);

    f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		f >> x >> y;

		//graf neorientat initial
		g[x].push_back(y);
		g[y].push_back(x);
	}

    out<<comp_conex;
}