Cod sursa(job #3202122)

Utilizator game_difficultyCalin Crangus game_difficulty Data 10 februarie 2024 18:07:58
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 100005;

vector<int> graf[N];

int n, m;
int depth[N];
bool visited[N];
int maxheight[N];
void dfs1(int x) {
	visited[x] = true;
	for (int muchie : graf[x]) {
		if (!visited[muchie]) {
			depth[muchie] = depth[x] + 1;
			dfs1(muchie);
		}
	}
}

int nr = 0;
vector<int> stiva;
vector<vector<int>> ans;
void dfs2(int x, int parent = 0) {
	visited[x] = true;
	stiva.push_back(x);
	for (int muchie : graf[x]) {
		if (!visited[muchie]) {
			dfs2(muchie, x);
			maxheight[x] = min(maxheight[muchie], maxheight[x]);
			if (maxheight[muchie] >= depth[x]) {
				nr++;
				ans.push_back({});
				while (stiva.back() != muchie) {
					ans.back().push_back(stiva.back());
					stiva.pop_back();
				}
				ans.back().push_back(muchie);
				stiva.pop_back();
				ans.back().push_back(x);
			}
		}
		else {
			if (muchie != parent)
				maxheight[x] = min(maxheight[muchie], maxheight[x]);
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		maxheight[i] = -1;
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	dfs1(1);
	for (int i = 1; i <= n; i++) {
		visited[i] = false;
		maxheight[i] = depth[i];
	}
	dfs2(1);
	cout << nr << '\n';
	for (vector<int>& componenta : ans) {
		for (int nod : componenta) {
			cout << nod << ' ';
		}
		cout << '\n';
	}
	return 0;
}