Pagini recente » Cod sursa (job #2872133) | Cod sursa (job #2326227) | Cod sursa (job #2887422) | Cod sursa (job #1676209) | Cod sursa (job #2716722)
//
// Created by mihai145 on 05.03.2021.
//
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int N, M;
vector <int> g[NMAX + 2];
vector<vector<int>> biconnectedComponents;
stack<int> st;
int _time, t[NMAX + 2], low[NMAX + 2];
void dfs(int node, int parent = -1) {
st.push(node);
_time++;
t[node] = low[node] = _time;
for(int son : g[node]) {
if(son != parent) {
if(t[son] != 0) {
low[node] = min(low[node], t[son]);
continue;
}
dfs(son, node);
low[node] = min(low[node], low[son]);
if(t[node] <= low[son]) {
vector<int> comp;
while(st.top() != node) {
comp.push_back(st.top());
st.pop();
}
comp.push_back(node);
biconnectedComponents.push_back(comp);
}
}
}
}
int main() {
cin >> N >> M;
for(int i = 1; i <= M; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
cout << (int)biconnectedComponents.size() << '\n';
for(vector<int> comp : biconnectedComponents) {
for(int vertex : comp) {
cout << vertex << ' ';
}
cout << '\n';
}
return 0;
}