Cod sursa(job #3215598)

Utilizator livliviLivia Magureanu livlivi Data 15 martie 2024 10:36:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
// #include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#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<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, int fiu) {
	bic.pb(vector<int>());

	int added = -1;
	while(!stk.empty() && added != fiu) {
		added = stk.top();
		bic.back().pb(added);
		stk.pop();
	}

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

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

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

			if(fiulrez == lvl[node]) {
				insert_(node, fiul);
			} 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;
}