Pagini recente » Cod sursa (job #2834352) | Cod sursa (job #2892349) | Cod sursa (job #1632428) | Cod sursa (job #2134346) | Cod sursa (job #2669142)
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<vector<int>> ans;
vector<bool> visited;
vector<int> reach;
vector<int> id;
stack<pair<int, int>> st;
void solver(int u, int v) {
ans.push_back(vector<int>{});
int comp_numer = (int)ans.size() - 1;
while (true) {
int x = st.top().first, y = st.top().second;
st.pop();
ans[comp_numer].push_back(x);
ans[comp_numer].push_back(y);
if (x == u && y == v) {
return;
}
}
}
void dfs(int u, int cnt) {
id[u] = reach[u] = cnt;
cnt += 1;
visited[u] = true;
for (int v : g[u]) {
if (!visited[v]) {
st.push(make_pair(u, v));
dfs(v, cnt);
reach[u] = min(reach[u], reach[v]);
if (reach[v] >= id[u]) {
solver(u, v);
}
} else {
reach[u] = min(reach[u], id[v]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ifstream in("biconex.in"); ofstream out("biconex.out");
int n, m; in >> n >> m;
g.resize(n);
visited.resize(n, false);
reach.resize(n);
id.resize(n);
for (int i = 0; i < m; ++i) {
int u, v; in >> u >> v;
u -= 1;
v -= 1;
g[u].push_back(v);
g[v].push_back(u);
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
dfs(i, cnt);
}
}
out << (int)ans.size() << "\n";
for (int i = 0; i < (int)ans.size(); ++i) {
sort(ans[i].begin(), ans[i].end());
ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
for (int value : ans[i]) {
out << 1 + value << " ";
}
out << "\n";
}
return 0;
}