Cod sursa(job #2810460)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 29 noiembrie 2021 15:21:48
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
#include<deque>
#include<set>
using namespace std;
int n, m, i, j, k, x, y, low[1000005], dfn[1000005],cnt;
bool ok;
vector<vector<int>>mu;
stack<int>st;
vector<set<int>>ans;
void afisare(int n) {
	while (st.top() != n) {
		ans[cnt].insert(st.top());
		st.pop();
	}
	ans[cnt].insert(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++) {
		for (auto x : ans[i])
			cout << x << " ";
		cout << "\n";
	}
}