Cod sursa(job #2645670)

Utilizator radustn92Radu Stancu radustn92 Data 29 august 2020 13:51:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int NMAX = 100505;

struct pathEntry {
	int node, nextIdx;
};

int N, M, components;
vector<int> G[NMAX];
stack<pathEntry> currPath;
bool visited[NMAX];

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	int x, y;
	for (int edge = 0; edge < M; edge++) {
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	for (int node = 1; node <= N; node++) {
		if (!visited[node]) {
			components++;
			currPath.push({node, 0});
			visited[node] = true;

			while (!currPath.empty()) {
				pathEntry& topEntry = currPath.top();
				if (topEntry.nextIdx != G[topEntry.node].size()) {
					int nextNeighb = G[topEntry.node][topEntry.nextIdx];
					topEntry.nextIdx++;
					if (!visited[nextNeighb]) {
						visited[nextNeighb] = true;
						currPath.push({nextNeighb, 0});
					}
				} else {
					currPath.pop();
				}
			}
		}
	}

	cout << components << "\n";
	return 0;
}