Pagini recente » Cod sursa (job #13985) | Cod sursa (job #2476524) | Cod sursa (job #2631188) | Cod sursa (job #609330) | Cod sursa (job #2698879)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5;
vector <int> G[Nmax];
int low[Nmax];
int lvl[Nmax];
stack < pair <int, int> > stk;
vector < vector <int> > bic_comp;
void get_comp(pair <int, int> stop_edge) {
vector <int> aux;
while (true) {
pair <int, int> tp = stk.top();
stk.pop();
aux.push_back(tp.first);
aux.push_back(tp.second);
if (tp == stop_edge)
break;
}
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(), aux.end()), aux.end());
bic_comp.push_back(aux);
}
void DFS(int node = 1, int parent = 0) {
lvl[node] = low[node] = lvl[parent] + 1;
for (int nei : G[node]) {
if (nei == parent)
continue;
if (!lvl[nei]) {
stk.push({node, nei});
DFS(nei, node);
low[node] = min(low[nei], low[node]);
if (low[nei] >= lvl[node]) // node punct critic
get_comp({node, nei});
}
else
low[node] = min(low[node], lvl[nei]);
}
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m;
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS();
cout << bic_comp.size() << '\n';
for (auto & line : bic_comp) {
for (int x : line)
cout << x << ' ';
cout << '\n';
}
return 0;
}