Pagini recente » Rating Patras Sanda (sanda-maria) | Cod sursa (job #3293938)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> graph[NMAX];
int depth[NMAX], low[NMAX];
bool vis[NMAX];
vector<int> stiva;
vector<vector<int>> bcc;
void pushBcc(int u, int v) {
vector<int> comp;
while(stiva.back() != v) {
comp.push_back(stiva.back());
stiva.pop_back();
}
comp.push_back(v);
comp.push_back(u);
stiva.pop_back();
bcc.push_back(comp);
}
void dfs(int node, int parent) {
static int time = 0;
depth[node] = low[node] = ++time;
stiva.push_back(node);
for(auto x : graph[node]) {
if(depth[x] == 0) {
dfs(x, node);
low[node] = min(low[node], low[x]);
if(low[x] >= depth[node]) {
pushBcc(node, x);
}
} else if(x != parent) {
if(depth[x] < depth[node]) {
low[node] = min(low[node], depth[x]);
}
}
}
}
int main() {
int n, m;
fin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b;
fin >> a >> b;
a--, b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(0, -1);
fout << bcc.size() << '\n';
for(auto comp : bcc) {
for(auto x : comp) {
fout << x + 1 << ' ';
}
fout << '\n';
}
return 0;
}