Pagini recente » Cod sursa (job #1922661) | Cod sursa (job #738319) | Cod sursa (job #521326) | Cod sursa (job #94343) | Cod sursa (job #3138808)
#include <bits/stdc++.h>
using namespace std;
string out[2]{ "No", "Yes" };
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const char sp = ' ';
const char nl = '\n';
const int inf = 1e9;
const int mod = 1e9 + 7;
#define all(x) x.begin(), x.end()
int n, m;
const int nmax = 1e5;
vector<int> g[nmax + 1];
vector<vector<int>> components;
int viz[nmax + 1]{0}, tin[nmax + 1]{0}, low[nmax + 1]{0};
int timer = 0;
stack<int> st;
void dfs(int v, int p = -1) {
viz[v] = 1;
tin[v] = low[v] = ++timer;
st.push(v);
for (auto& u : g[v]) {
if (u == p) {
continue;
}
// back edge
if (viz[u]) {
low[v] = min(low[v], tin[u]);
}
else {
dfs(u, v);
low[v] = min(low[v], low[u]);
if (low[u] >= tin[v]) {
components.push_back({});
while (st.top() != u) {
components.back().push_back(st.top());
st.pop();
}
components.back().push_back(u);
components.back().push_back(v);
st.pop();
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs(i);
}
}
fout << components.size() << nl;
for (auto& c : components) {
for (auto& x : c) {
fout << x << sp;
}
fout << nl;
}
}