Pagini recente » Cod sursa (job #722144) | Cod sursa (job #1754330) | Cod sursa (job #1005216) | Cod sursa (job #2191014) | Cod sursa (job #3030819)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif // LOCAL
const int NMAX =1e5 + 7;
int depth[NMAX], low[NMAX], visited[NMAX], parent[NMAX];
vector<int> g[NMAX];
vector<int> ap;
vector<int> stiva;
vector<vector<int>> bicomp;
void dfs(int node, int d) {
depth[node] = d;
low[node] = d;
int children = 0;
bool is_articulation = false;
stiva.push_back(node);
for(auto vec : g[node]) {
if(depth[vec] == 0) {
parent[vec] = node;
dfs(vec, d + 1);
children += 1;
if(low[vec] >= depth[node]) {
is_articulation = true;
vector<int> comp;
while(!stiva.empty() && stiva.back() != vec) {
comp.push_back(stiva.back());
stiva.pop_back();
}
stiva.pop_back();
comp.push_back(vec);
comp.push_back(node);
bicomp.push_back(comp);
}
low[node] = min(low[node], low[vec]);
}
else if(vec != parent[node]) {
low[node] = min(low[node], depth[vec]);
}
}
if(parent[node] != 0 && is_articulation) {
ap.push_back(node);
}
if(parent[node] == 0 && children > 1) {
ap.push_back(node);
}
}
int main()
{
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++) {
if(depth[i] == 0) dfs(i, 1);
}
cout << bicomp.size() << '\n';
for(auto e : bicomp) {
for(auto ee : e) cout << ee << " ";
cout << '\n';
}
return 0;
}