Pagini recente » Cod sursa (job #1773870) | Cod sursa (job #726664) | Cod sursa (job #2882784) | Cod sursa (job #1824472) | Cod sursa (job #2837080)
#include <bits/stdc++.h>
using namespace std;
#define cin fin
#define cout fout
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define stack incaasteptgluma8
const int nmax = 1e5 + 5;
const int mmax = 2e5 + 5;
int n, m;
struct edg {
int u, v, other;
bool operator !=(const edg& a) const {
return pair<int,int>{u,v} != pair<int,int>{a.u,a.v};
}
} edge[mmax];
vector< vector<int> > bicon;
vector<int> stack;
vector<int> graph[nmax];
int occ[nmax];
static void redux(edg left) {
bicon.push_back(vector<int>());
while(stack.size() && edge[stack.back()] != left) {
bicon.back().push_back(edge[stack.back()].u);
bicon.back().push_back(edge[stack.back()].v);
stack.pop_back();
}
bicon.back().push_back(edge[stack.back()].u);
bicon.back().push_back(edge[stack.back()].v);
stack.pop_back();
return;
}
int depth[nmax];
int maxdepth[nmax];
static void dfs(int node, int f) {
int c;
depth[node] = depth[f] + 1;
maxdepth[node] = depth[node];
occ[node] = 1;
for(auto x : graph[node]) {
c = edge[x].other ^ node;
if(c == f)
continue;
if(!occ[c]) {
stack.push_back(x);
dfs(c, node);
maxdepth[node] = min(maxdepth[node], maxdepth[c]);
if(maxdepth[c] >= depth[node]) {
redux(edge[x]);
}
}
else
maxdepth[node] = min(maxdepth[node], depth[c]);
}
return;
}
int main() {
cin >> n >> m;
for(int i = 0, x, y; i < m; i++) {
cin >> x >> y;
--x;
--y;
if(x > y)
swap(x, y);
edge[i] = edg{x, y, x ^ y};
graph[x].push_back(i);
graph[y].push_back(i);
}
dfs(0,0);
cout << bicon.size() << '\n';
for(auto x :bicon) {
sort(x.begin(), x.end());
x.resize(distance(x.begin(),unique(x.begin(), x.end())));
for(auto y : x)
cout << y + 1 << ' ';
cout << '\n';
}
}