Pagini recente » Cod sursa (job #2082291) | Cod sursa (job #885539) | Cod sursa (job #2705836)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
int n, m;
vector<int> a[100001], dfn(100001), low(100001);
stack<pair<int, int>> st;
vector<int> C[100001];
int compbiconx;
void read() {
int x, y, i;
ifstream f("biconex.in");
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> x >> y;
a[x].emplace_back(y);
a[y].emplace_back(x);
}
f.close();
}
void inreg(int px, int x) {
int i;
vector<int> con; int cpx, cx;
do {
cpx = st.top().first, cx = st.top().second;
st.pop();
con.emplace_back(cpx); con.emplace_back(cx);
} while (px != cpx && x != cx);
sort(con.begin(), con.end());
C[compbiconx].emplace_back(con[0]);
for (i = 1; i < con.size(); i++)
if (con[i] != con[i - 1])
C[compbiconx].emplace_back(con[i]);
compbiconx++;
}
void dfs(int x, int px, int nr) {
int i;
dfn[x] = low[x] = nr;
for (i = 0; i < a[x].size(); i++) {
if (a[x][i] == px)
continue;
if (dfn[a[x][i]] == 0) {
st.push({x, a[x][i]});
dfs(a[x][i], x, nr + 1);
low[x] = min(low[x], low[a[x][i]]);
if (low[a[x][i]] >= dfn[x])
inreg(x, a[x][i]);
}
else low[x] = min(low[x], dfn[a[x][i]]);
}
}
void solve() {
int i;
dfs(1, 0, 1);
}
void output() {
int i, j;
ofstream g("biconex.out");
g << compbiconx << '\n';
for (i = 0; i < compbiconx; i++) {
sort(C[i].begin(), C[i].end());
for (j = 0; j < C[i].size(); j++)
g << C[i][j] << ' ';
g << '\n';
}
g.close();
}
int main() {
read();
solve();
output();
return 0;
}