Cod sursa(job #944110)

Utilizator sorin2kSorin Nutu sorin2k Data 27 aprilie 2013 14:30:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<vector>
using namespace std;

int *vizitat;
int nrCompCon = 0;

void DFS(vector<int> *adj, int start)
{
	int i;
	for(i = 0; i < (int)adj[start].size(); i++)
	{
		if(vizitat[adj[start][i]] == 0)
		{
			vizitat[adj[start][i]] = 1;
			DFS(adj, adj[start][i]);
		}
	}
}

int main()
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int n, m, u, v, i;
	fin >> n >> m;
	vector<int> *adj = new vector<int>[n];
	for(i = 0; i < m; i++)
	{
		fin >> u >> v;
		u--; 
		v--; // retinem nodurile de la 0 la n - 1
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vizitat = new int[n];
	for(i = 0; i < n; i++)
		vizitat[i] = 0;
	for(i = 0; i < n; i++)
		if(vizitat[i] == 0)
		{
			nrCompCon++;
			vizitat[i] = 1;
			DFS(adj, i);
		}
	fout << nrCompCon;
	return 0;
}