Pagini recente » Cod sursa (job #696851) | Cod sursa (job #2758560) | Cod sursa (job #2517069) | Cod sursa (job #1230629) | Cod sursa (job #2981748)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int kN = 1e5 + 5;
vector<vector<int>>biconex;
vector<pair<int, int>>critics;
vector<int>g[kN];
int n, m, t;
int low[kN], tin[kN], stk[kN];
bool visited[kN], art[kN];
vector<int>add (int x, int y){
vector<int>ans;
while (stk[stk[0]] != y){
ans.push_back(stk[stk[0]]);
--stk[0];
}
ans.push_back(x);
ans.push_back(y);
--stk[0];
return ans;
}
void dfs (int nod, int dad = -1){
stk[++stk[0]] = nod;
visited[nod] = true;
tin[nod] = low[nod] = ++t;
int children = 0;
for (int u : g[nod]){
if (u == dad){
continue;
}
if (visited[u]){
low[nod] = min(low[nod], tin[u]);
}
else{
dfs(u, nod);
low[nod] = min(low[nod], low[u]);
if (low[u] > tin[nod]){
critics.push_back(make_pair(nod, u));
}
if (low[u] >= tin[nod] && dad != -1){
art[nod] = true;
}
if (low[u] >= tin[nod]){
biconex.push_back(add(nod, u));
}
++children;
}
}
if (dad == -1 && children > 1){
art[nod] = true;
}
}
int main(){
ios_base::sync_with_stdio(false);
fin >> n >> m;
for (int i = 1; i <= m; i++){
int x, y; fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; i++){
if (!visited[i]){
dfs(i);
}
}
fout << (int)biconex.size() << '\n';
for (auto y : biconex){
sort(y.begin(), y.end());
for (int x : y){
fout << x << " ";
}
fout << '\n';
}
}