Pagini recente » Cod sursa (job #654073) | Cod sursa (job #376630) | Cod sursa (job #1340299) | Solutia problemei shoturi | Cod sursa (job #2938280)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 1e5;
int N, M;
vector<int> adj[NMAX + 1];
int lev[NMAX + 1], low[NMAX + 1];
stack<int> st;
vector<vector<int>> bicomp;
void dfs(int u = 1, int v = 0) {
lev[u] = low[u] = lev[v] + 1;
st.push(u);
for(const auto &it: adj[u]) if(it != v) {
if(lev[it] == 0) {
dfs(it, u);
low[u] = min(low[u], low[it]);
if(low[it] >= lev[u]) {
bicomp.push_back({it, u});
while(!st.empty() && st.top() != it) {
bicomp.back().push_back(st.top());
st.pop();
}
st.pop();
}
} else {
low[u] = min(low[u], lev[it]);
}
}
}
int main() {
ios_base :: sync_with_stdio(false);
fin >> N >> M;
for(int i = 1; i <= M; i++) {
int u, v;
fin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs();
fout << bicomp.size() << '\n';
for(auto &comp: bicomp) {
for(const auto &it: comp) {
fout << it << " ";
}
fout << '\n';
}
fin.close();
fout.close();
return 0;
}