Pagini recente » Cod sursa (job #934768) | Cod sursa (job #2244668) | Cod sursa (job #16551) | Cod sursa (job #2922920) | Cod sursa (job #1166713)
#include <algorithm>
#include <bitset>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
typedef pair<int, int> pii;
#define x first
#define y second
const int MAX_N = 100100;
int N, M;
vector<int> graph[MAX_N];
bitset<MAX_N> vis;
vector<pii> st;
vector<vector<int>> ans;
int depth[MAX_N], lowest[MAX_N];
void dfs(int node);
void flush_biconex(pii e);
int main() {
fin >> N >> M;
for (int i = 1, a, b; i <= M; i += 1) {
fin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1);
fout << ans.size() << '\n';
for (auto i: ans) {
for (auto j: i) {
fout << j << ' ';
}
fout << '\n';
}
}
void dfs(int node) {
vis[node] = 1;
lowest[node] = depth[node];
for (auto x: graph[node]) {
if (vis[x]) {
lowest[node] = min(lowest[node], depth[x]);
continue;
}
depth[x] = depth[node] + 1;
st.push_back(make_pair(node, x));
dfs(x);
if (lowest[x] >= depth[node])
flush_biconex(make_pair(node, x));
lowest[node] = min(lowest[node], lowest[x]);
}
}
inline void flush_biconex(pii e) {
ans.push_back(vector<int>());
vector<int> &c = ans.back();
while (st.back() != e) {
c.push_back(st.back().x);
c.push_back(st.back().y);
st.pop_back();
}
c.push_back(st.back().x);
c.push_back(st.back().y);
st.pop_back();
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
}