Cod sursa(job #2986550)

Utilizator tudor036Borca Tudor tudor036 Data 28 februarie 2023 19:14:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define NMAX 100000

using namespace std;

ifstream F("dfs.in");
ofstream G("dfs.out");

vector<vector<int>> g;
int usedNode[NMAX + 2];

int N, M, components = 0;

void initializeDS() {
	g.resize(N + 1);
}

void Read() {
	int x, y;
	F >> N >> M;

	initializeDS();

	while (M--) {
		F >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	F.close();
}

void DFS(int sourceNode) {
	int currentPivotNode, currentNode;
	stack<int> st;

	st.push(sourceNode);
	usedNode[sourceNode] = 1;

	while (!st.empty()) {
		currentPivotNode = st.top();
		st.pop();

		if (!usedNode[currentPivotNode]) {
			usedNode[currentPivotNode] = 1;
		}

		for (int currentNode : g[currentPivotNode]) {
			if (!usedNode[currentNode]) {
				st.push(currentNode);
			}
		}
	}
}

void Solve() {
	int i = 1;
	while (i <= N) {
		DFS(i);
		components++;
		do {
			i++;
		} while (usedNode[i] == 1);
	}
}

void Print() {
	G << components;

	G.close();
}

int main()
{
	Read();
	Solve();
	Print();

	return 0;
}