Cod sursa(job #3264575)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 22 decembrie 2024 15:17:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <unordered_set>

using namespace std;

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

const int NMAX = 1e5;

int n, m, t, ind_edges, ind_bcc;
vector<int> g[NMAX + 1];
int low[NMAX + 1];
int dfs_time[NMAX + 1];
pair<int, int> edges[NMAX + 1];
unordered_set<int> bcc[NMAX + 1];

void GetBCC(pair<int, int> root_edge) {
	ind_bcc++;
	while (edges[ind_edges] != root_edge) {
		bcc[ind_bcc].insert(edges[ind_edges].first);
		bcc[ind_bcc].insert(edges[ind_edges].second);
		ind_edges--;
	}
	bcc[ind_bcc].insert(edges[ind_edges].first);
	bcc[ind_bcc].insert(edges[ind_edges].second);
	ind_edges--;
}

void DFS(int node, int dad = 0) {
	dfs_time[node] = low[node] = ++t;
	for (int next_node : g[node]) {
		if (next_node != dad && dfs_time[next_node] < dfs_time[node]) {
			// Take this edge if it doesn't point to dad and it has not been added to the stack
			// 1. dfs_time[next_node] = 0, then its a forward edge
			// 2. dfs_time[next_node] != 0, then its a back edge and we choose to add it in this orientation
			//	  Making it to be added only once in the stack.
			edges[++ind_edges] = { node, next_node };
		}

		if (!low[next_node]) {
			DFS(next_node, node);
			//edges[++ind_edge] = { node, next_node };
			low[node] = min(low[node], low[next_node]);
			if (low[next_node] >= dfs_time[node]) {
				GetBCC({ node, next_node });
			}
		}
		else if (next_node != dad) {
			low[node] = min(low[node], dfs_time[next_node]);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	for (int i = 1; i <= n; i++) {
		if (!low[i]) {
			DFS(i);
		}
	}

	cout << ind_bcc << '\n';
	for (int i = 1; i <= ind_bcc; i++, cout << '\n') {
		for (int x : bcc[i]) {
			cout << x << ' ';
		}
	}

	return 0;
}