Pagini recente » Cod sursa (job #3238910) | Cod sursa (job #1554194) | Borderou de evaluare (job #2078596) | Cod sursa (job #3255022) | Cod sursa (job #2195773)
#include <bits/stdc++.h>
#define fi first
#define se second
#define N 100100
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m, x, y, S, low[N], timp[N], cnt[N], timer;
vector <int> v[100100];
bitset <100100> viz;
vector <vector <int> > sol;
vector <pair <int, int> > edges;
void biconnect(pair <int, int> edge){
vector <int> aux;
while(edges.back() != edge){
aux.push_back(edges.back().se);
edges.pop_back();
}
aux.push_back(edges.back().se);
aux.push_back(edges.back().fi);
edges.pop_back();
sol.push_back(aux);
aux.clear();
}
void dfs(int dad, int from){
viz[from] = 1;
low[from] = timp[from] = ++timer;
for(auto to : v[from]){
if(to == dad)
continue;
if(!viz[to]){
edges.push_back({from, to});
dfs(from, to);
if(from == S || timp[from] <= low[to]){
cnt[from]++;
biconnect({from, to});
} else low[from] = min(low[from], low[to]);
} else low[from] = min(low[from], timp[to]);
}
}
int main(){
in >> n >> m;
while(m--){
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz[i]){
S = i;
cnt[S] = -1;
dfs(0, S);
}
out << sol.size();
for(int i = 0; i < sol.size(); i++){
out << '\n';
for(auto j : sol[i])
out << j << ' ';
}
return 0;
}