Cod sursa(job #3215594)

Utilizator livliviLivia Magureanu livlivi Data 15 martie 2024 10:28:50
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <stack>

#define pb push_back

// #define fin cin
// #define fout cout

using namespace std;

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

const int nmax = 1e5;

vector<int> edge[nmax + 1];
vector<vector<int>> bic;
vector<bool> viz(nmax + 1);
vector<int> lvl(nmax + 1);
stack<pair<int, int>> stk;
int n, m, x, y;

void read() {
	fin >> n >> m;
	for(int i = 1; i <= m; i++) {
		fin >> x >> y;
		edge[x].pb(y);
		edge[y].pb(x);
	}
}

void insert_(int node) {
	bic.pb(vector<int>());

	int padre = stk.top().second;

	while(!stk.empty() && padre != node) {
		bic.back().pb(stk.top().second);
		padre = stk.top().first;
		stk.pop();
	}

	bic.back().pb(node);
}

int dfs(int node) {
	viz[node] = 1;
	int highest = lvl[node] - 1;

	for(auto fiul : edge[node]) {
		if(viz[fiul])
			highest = min(highest, lvl[fiul]);
		else {
			lvl[fiul] = lvl[node] + 1;
			stk.push({node, fiul});
			int fiulrez = dfs(fiul);

			if(fiulrez == lvl[node]) {
				insert_(node);
			} else
				highest = min(highest, fiulrez);
		}
	}

	return highest;
}

int main() {
	read();
	dfs(1);

	fout << bic.size() << "\n";
	for(int i = 0; i < bic.size(); i++) {
		for(auto val : bic[i])
			fout << val << " ";
		fout << "\n";
	}
	return 0;
}