Pagini recente » Profil Simon2712 | Borderou de evaluare (job #1620587) | Profil Simon2712 | Cod sursa (job #2012378)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100000 + 5;
const int MMAX = 100000 + 5;
struct Edge {
int a, b;
inline int other(int node) {
return a ^ b ^ node;
}
} edges[MMAX];
vector <int> graph[NMAX];
int h[NMAX];
int low[NMAX];
bool vis[NMAX];
stack <int> stk;
vector <vector <int> > bic;
void dfs(int node, int fatherEdge) {
vis[node] = true;
//bool isCritical = false;
int sons = 0;
for (auto it: graph[node]) {
int son = edges[it].other(node);
if (!vis[son]) {
++ sons;
h[son] = low[son] = 1 + h[node];
stk.push(it);
dfs(son, it);
low[node] = min(low[node], low[son]);
//Critical edge
//if (low[son] > h[node])
// cout << "Critical " << edges[it].a << ' ' << edges[it].b << endl;
//Critical node
//if (low[son] >= h[node])
// isCritical = true;
if (low[son] >= h[node]) {
bic.push_back(vector <int>());
int last;
do {
last = stk.top();
stk.pop();
bic.back().push_back(edges[last].a);
bic.back().push_back(edges[last].b);
} while (last != it);
vector <int> &v = bic.back();
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
}
}
else if (h[son] < h[node] && it != fatherEdge) {
low[node] = min(low[node], h[son]);
//stk.push(it);
}
}
//Critical node
/*if (fatherEdge == 0) {
if (sons > 1)
cout << "Critical node " << node << endl;
}
else if (isCritical)
cout << "Critical node " << node << endl;*/
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int N, M;
cin >> N >> M;
for (int i = 1; i <= M; ++ i) {
cin >> edges[i].a >> edges[i].b;
if (edges[i].a != edges[i].b) {
graph[edges[i].a].push_back(i);
graph[edges[i].b].push_back(i);
}
}
dfs(1, 0);
cout << bic.size() << '\n';
for (auto it: bic)
for (int i = 0; i < it.size(); ++ i)
cout << it[i] << " \n"[i + 1 == it.size()];
return 0;
}