Cod sursa(job #2666023)

Utilizator TheSharkCristian-Andrei Ionescu TheShark Data 31 octombrie 2020 17:58:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100001
#define DEFAULT_DISCOVERY_TIMES -1

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> adjList[NMAX];
int discoveryTimes[NMAX], low[NMAX];
stack<pair<int, int>> pairs;
vector<vector<int>> results;

bool isDiscovered(int node) {
	return discoveryTimes[node] != DEFAULT_DISCOVERY_TIMES;
}


void biconex(int lowX, int lowY) {
	vector<int> temp;

	int x, y;
	do {
		x = pairs.top().first;
		y = pairs.top().second;

		pairs.pop();
		temp.push_back(y);
	} while (lowX != x && lowY != y);

	temp.push_back(x);

	results.push_back(temp);
}

void dfs(int startNode, int parent, int no) {
	discoveryTimes[startNode] = low[startNode] = no;

	for (const auto& node : adjList[startNode]) {
		if (node != parent) {
			if (!isDiscovered(node)) {
				pairs.push(make_pair(startNode, node));
				dfs(node, startNode, no + 1);

				if (low[startNode] > low[node]) {
					low[startNode] = low[node];
				}
				if (low[node] >= discoveryTimes[startNode]) {
					biconex(startNode, node);
				}
			}
			else {
				low[startNode] = min(low[startNode], discoveryTimes[node]);
			}
		}
	}
}

int main() {

	int N, M;

	in >> N >> M;
	for (int i = 0; i < M; ++i) {
		int startNode, endNode;
		in >> startNode >> endNode;
		adjList[startNode].push_back(endNode);
		adjList[endNode].push_back(startNode);
	}

	for (int i = 1; i <= N; i++) {
		discoveryTimes[i] = DEFAULT_DISCOVERY_TIMES;
	}

	dfs(1, 0, 0);
	out << results.size() << '\n';
	for (const auto& result : results) {
		for (const auto& node : result) {
			out << node << ' ';
		}
		out << '\n';
	}

	return 0;
}