Pagini recente » Cod sursa (job #2519461) | Cod sursa (job #495980) | Cod sursa (job #545977) | Cod sursa (job #2249151) | Cod sursa (job #2682259)
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
int n, m, cnt;
vector < int > V[100100], R[100100];
bitset < 100100 > B;
int dad[100100], d[100100], low[100100];
stack < PII > S;
void get_component(PII m) {
++cnt;
while (S.top() != m) {
auto e = S.top();
S.pop();
R[cnt].push_back(e.second);
}
auto e = S.top();
S.pop();
R[cnt].push_back(e.first);
R[cnt].push_back(e.second);
}
void find_biconex(int x, int parent, int depth) {
B[x] = 1;
d[x] = depth;
low[x] = depth;
for (auto it : V[x]) {
if (!B[it]) {
S.push({x, it});
find_biconex(it, x, depth + 1);
low[x] = min(low[x], low[it]);
if (parent == -1 && V[x].size() > 1) {
get_component({x, it});
} else if (low[it] >= depth) {
get_component({x, it});
}
} else if (it != parent) {
low[x] = min(low[x], d[it]);
}
}
}
int main(){
ifstream cin("biconex.in");
ofstream cout("biconex.out");
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!B[i]) {
find_biconex(i, -1, 1);
}
}
cout << cnt << "\n";
for (int i = 1; i <= cnt; i++) {
for (auto it : R[i]) {
cout << it << " ";
}
cout << "\n";
}
return 0;
}