Cod sursa(job #1751857)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 2 septembrie 2016 08:59:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <queue>

using namespace std;

typedef struct adjNode
{
	int identifier;
	struct adjNode *next;

	public:
		adjNode(int id, struct adjNode* next) : identifier(id), next(next){}
}AdjNode;

AdjNode** ReadAdjencyLists(int n, int m, istream &fin);
void Dfs(int s, AdjNode** adjencyLists, bool* flagVector);

int main()
{
	ifstream fin;
	ofstream fout;
	fout.open("dfs.out");
	fin.open("dfs.in");

	int n, m;
	fin >> n >> m;

	AdjNode** adjencyLists =  ReadAdjencyLists(n, m, fin);

	bool* flagVector = new bool[n + 1]();
	int conexComp = 0;
	for(int i = 1; i <= n; i++)
	{
		if(!flagVector[i])
		{
			conexComp++;
			flagVector[i] = true;
			Dfs(i, adjencyLists, flagVector);
		}
	}

	fout << conexComp;

	fin.close();
	fout.close();
	return 0;
}

AdjNode** ReadAdjencyLists(int n, int m, istream &fin)
{
	AdjNode** adjencyLists = new AdjNode*[n + 1]();
	int x, y;

	for(int i = 1; i <= m; i++)
	{
		fin >> x >> y;
		AdjNode* xToyArc = new AdjNode(y, adjencyLists[x]);
		adjencyLists[x] = xToyArc;
		AdjNode* yToxArc = new AdjNode(x, adjencyLists[y]);
		adjencyLists[y] = yToxArc;
	}

	return adjencyLists;
}

void Dfs(int s, AdjNode** adjencyLists, bool* flagVector)
{
	AdjNode* current = adjencyLists[s];

	while(current)
	{
		if(!flagVector[current->identifier])
		{
			flagVector[current->identifier] = true;
			Dfs(current->identifier, adjencyLists, flagVector);
		}

		current = current->next;
	}
}