Cod sursa(job #3364279)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 1 septembrie 2026 10:57:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
#if USE_STD_IO
#define fin cin
#define fout cout
#else
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#endif

typedef struct {
	int nod;
	int fiu; // vector<int>::iterator mch;
} ElementStruct;

int n, m, i;
vector<int> gr[200002];
int mi[200002];
int tur[200002];

stack<ElementStruct> stiv;

vector<vector<int>> comp;

static inline int Min(const int a, const int b) {
	return (a < b ? a : b);
}

static inline void DFS(const int nod, const int niv) {
	mi[nod] = tur[nod] = niv;
	for(const int fiu : gr[nod]) {
		if(0 == tur[fiu]) {
			stiv.push({nod, fiu});
			DFS(fiu, niv + 1);
			mi[nod] = Min(mi[nod], mi[fiu]);

			if(mi[fiu] >= tur[nod]) {
				comp.push_back(vector<int>{});

				int x, y;
				do {
					x = stiv.top().nod;
					y = stiv.top().fiu;
					stiv.pop();
					comp.back().push_back(x);
					comp.back().push_back(y);
				}
				while(nod != x || fiu != y);
			}
		}
		else {
			mi[nod] = Min(mi[nod], tur[fiu]);
		}
	}
}

int main() {
	#if USE_STD_IO
	ios_base::sync_with_stdio(false);
	#endif
	fin.tie(NULL);
	fout.tie(NULL);

	fin >> n >> m;
	for(i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	DFS(1, 1);
	fout << comp.size() << '\n';
	for(vector<int>& compCur : comp) {
		sort(compCur.begin(), compCur.end());

		compCur.erase(
			unique(compCur.begin(), compCur.end()),
					  compCur.end());

		for(const int cur : compCur) fout << cur << ' ';
		fout << '\n';
	}

	return 0;
}