Cod sursa(job #2810451)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 29 noiembrie 2021 15:07:24
Problema Componente biconexe Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#include<deque>
using namespace std;
int n, m, i, j, k, x, y, low[10005], dfn[10005] = { (-1) },cnt;
bool ok;
vector<vector<int>>mu;
stack<int>st;
vector<deque<int>>ans;
void afisare(int n) {
	while (st.top() != n) {
		ans[cnt].emplace_front(st.top());
		st.pop();
	}
	ans[cnt].emplace_front(n);
	cnt++;
}
void DFS(int nod, int back, int nr) {
	dfn[nod] = low[nod] = nr;
	for (auto k : mu[nod])
	{
		if (k == back) continue;
		if (dfn[k] == -1) {
			st.push(k);
			DFS(k, nod, nr + 1);
			low[nod] = min(low[k], low[nod]);
			if (low[k] >= dfn[nod])
				afisare(nod);
		}
		else low[nod] = min(low[nod], dfn[k]);
	}

}
int main() {
	ifstream cin("biconex.in");
	ofstream cout("biconex.out");
	cin >> n >> m;
	mu.resize(m);
	ans.resize(n);
	for (i = 1;i <= m;i++)
	{
		dfn[i] = -1;
		cin >> x >> y;
		mu[x].emplace_back(y);
		mu[y].emplace_back(x);
	}
	st.push(1);
	DFS(1, 0, 0);
	cout << cnt << '\n';
	for (i = 0;i < cnt;i++) {
		while (ans[i].empty() != 1) {
			cout << ans[i].front() << " ";
			ans[i].pop_front();
		}
		cout << "\n";
	}
}