Pagini recente » Cod sursa (job #1441854) | Cod sursa (job #2251390) | Cod sursa (job #2566557) | Cod sursa (job #2093165) | Cod sursa (job #3332396)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
vector<int> adj[MAXN+1];
int disc[MAXN+1], low[MAXN+1], timer;
stack<pair<int,int>> st;
vector<vector<int>> bcc;
void dfs(int u, int p) {
disc[u] = low[u] = ++timer;
for (int v : adj[u]) {
if (!disc[v]) {
st.push({u,v});
dfs(v,u);
low[u] = min(low[u], low[v]);
if (low[v] >= disc[u]) {
vector<int> comp;
while (!st.empty()) {
auto e = st.top(); st.pop();
comp.push_back(e.first);
comp.push_back(e.second);
if (e.first == u && e.second == v) break;
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
bcc.push_back(comp);
}
} else if (v != p && disc[v] < disc[u]) {
st.push({u,v});
low[u] = min(low[u], disc[v]);
}
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
fin >> n >> m;
for (int i=0;i<m;i++) {
int x,y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i=1;i<=n;i++) if (!disc[i]) dfs(i,-1);
fout << bcc.size() << "\n";
for (auto &comp : bcc) {
for (int v : comp) fout << v << " ";
fout << "\n";
}
return 0;
}