Cod sursa(job #3211698)

Utilizator vladdobro07vladdd vladdobro07 Data 10 martie 2024 01:08:07
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define pb push_back

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) {
	bic.pb(vector<int>());

	while(!stk.empty() && stk.top() != node) {
		bic.back().pb(stk.top());
		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);
			else
				highest = min(highest, fiulrez);
		}
	}

	return highest;
}

int main() {
	read();
	edge[0].pb(1);
	int asa_si = dfs(0);
	bic.pop_back();

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