Pagini recente » Cod sursa (job #284204) | Cod sursa (job #217461) | Cod sursa (job #3003224) | Cod sursa (job #2067435) | Cod sursa (job #1923340)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000 + 5;
const int MMAX = 2 * NMAX;
struct Edge {
int a, b;
Edge(int _a = 0, int _b = 0):
a(_a), b(_b) {}
inline int other(int node) {
return a ^ b ^ node;
}
} edges[MMAX];
int N, M;
vector <int> graph[NMAX];
bool vis[NMAX];
int h[NMAX];
int low[NMAX];
stack <int> stk;
vector <vector <int> > bicos;
void extract(int edg) {
vector <int> sol;
while (stk.top() != edg) {
sol.push_back(edges[stk.top()].a);
sol.push_back(edges[stk.top()].b);
stk.pop();
}
sol.push_back(edges[stk.top()].a);
sol.push_back(edges[stk.top()].b);
stk.pop();
bicos.push_back(sol);
}
void dfs(int node) {
vis[node] = true;
for (auto it: graph[node]) {
int son = edges[it].other(node);
if (!vis[son]) {
h[son] = low[son] = h[node] + 1;
stk.push(it);
dfs(son);
if (low[son] >= h[node])
extract(it);
else if (low[son] < low[node])
low[node] = low[son];
}
else {
if (h[son] < low[node])
low[node] = h[son];
}
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
cin >> N >> M;
for (int i = 1; i <= M; ++ i) {
int a, b;
cin >> a >> b;
edges[i].a = a, edges[i].b = b;
graph[a].push_back(i);
graph[b].push_back(i);
}
for (int i = 1; i <= N; ++ i)
if (!vis[i])
dfs(i);
cout << bicos.size() << '\n';
for (auto &it: bicos) {
sort(it.begin(), it.end());
it.resize(unique(it.begin(), it.end()) - it.begin());
for (int i = 0; i < it.size(); ++ i)
cout << it[i] << " \n"[i + 1 == it.size()];
}
return 0;
}