Pagini recente » Cod sursa (job #2744416) | Cod sursa (job #1948475) | Cod sursa (job #2967913) | Cod sursa (job #1155632) | Cod sursa (job #3142374)
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define NMAX (int)(1e5 + 5)
#define MMAX (int)(2e5 + 5)
#define INF (int)(1e9)
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {
cerr << '{';
__print(std::get<0>(x));
cerr << ',';
__print(std::get<1>(x));
cerr << ',';
__print(std::get<2>(x));
cerr << '}';
}
template<typename T, typename V>
void __print(const pair<T, V> &x) {
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template<typename T>
void __print(const T &x) {
int f = 0;
cerr << '{';
for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) {
__print(t);
if (sizeof...(v)) cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
int T, N, M;
int low[NMAX];
int h[NMAX];
// int edges[MMAX][MMAX];
bool viz[NMAX];
vector<vector<int>> bic;
vector<int> G[NMAX]; // G[u] = i => node `u` is one endpoint of the `i`th edge; e[it].other(u) = v => (u, v) edge; the `it`th one
stack<int> st;
struct Edge {
int u, v, c;
int other(const int node) { // node = u => ret. v; node = v => ret. u (return the other endpoint of the edge)
return u ^ v ^ node;
}
} e[MMAX];
void dfs (int u, int parent_edge_id) {
viz[u] = true;
for (const auto &i: G[u]) { // edge (u, v)
int v = e[i].other(u);
if (!viz[v]) {
st.push(i);
h[v] = low[v] = h[u] + 1;
dfs(v, i);
low[u] = min(low[u], low[v]);
if (low[v] >= h[u]) {
vector<int> comp{};
int prev_top = -1;
do {
prev_top = st.top(); st.pop();
int x = e[prev_top].u; int y = e[prev_top].v;
comp.push_back(x); comp.push_back(y);
} while (prev_top != i);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
bic.push_back(comp);
}
}
else { // muchie de intoarcere
low[u] = min(low[u], h[v]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
memset(e, -1, sizeof(e));
cin >> N >> M;
for (int i = 0; i < M; ++i) {
cin >> e[i].u >> e[i].v; // >> e[i].c;
// edges[e[i].u][e[i].v] = e[i].c;
G[e[i].u].push_back(i);
G[e[i].v].push_back(i);
}
dfs(1, 0);
cout << bic.size() << '\n';
for (const auto &comp: bic) {
for (const auto &x: comp) cout << x << ' ';
cout << '\n';
}
return 0;
}