Pagini recente » Cod sursa (job #2170329) | Cod sursa (job #2327877) | Cod sursa (job #98033) | Cod sursa (job #912519) | Cod sursa (job #3123298)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
#define NMAX 100001
struct Edge {
int u, v;
};
vector<int> dis(NMAX, -1);
vector<int> low(NMAX, -1);
vector<bool> vis(NMAX, false);
stack<Edge> st;
vector<set<int> > ans;
void biconex(int node, int parent, int time, vector<int> adj[NMAX]) {
dis[node] = low[node] = ++time;
vis[node] = true;
for (auto neigh : adj[node]) {
if (neigh == parent) {
continue;
}
if (vis[neigh]) {
low[node] = min(low[node], dis[neigh]);
} else {
Edge e;
e.u = node;
e.v = neigh;
st.push(e);
biconex(neigh, node, time, adj);
low[node] = min(low[node], low[neigh]);
if (low[neigh] >= dis[node]) {
int u = 0, v = 0;
set<int> p;
do {
u = st.top().u;
v = st.top().v;
p.insert(u);
p.insert(v);
st.pop();
} while (u != node && v != neigh);
ans.push_back(p);
}
}
}
}
void print() {
ofstream fout("biconex.out");
fout << ans.size() << "\n";
for (auto p : ans) {
for (auto x : p) {
fout << x << " ";
}
fout << "\n";
}
}
int main() {
ifstream fin("biconex.in");
int n, m;
fin >> n >> m;
vector<int> adj[n + 1];
for (int i = 1, x, y; i <= m; ++i) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
biconex(1, -1, 0, adj);
print();
return 0;
}