Pagini recente » Cod sursa (job #2271861) | Cod sursa (job #670786) | Cod sursa (job #2491219) | Cod sursa (job #2366877) | Cod sursa (job #3203613)
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#pragma GCC optimize ("O3")
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
const int LIM = 300000;
int n, m;
vector<int> edge[LIM + 5];
int cbc;
vector<int> CBC[LIM + 5];
int lvl[LIM + 5], low[LIM + 5];
bitset<LIM + 5> viz;
stack<int> stk;
inline void tarjan(int crt, int prv, int level){
viz[crt] = true;
lvl[crt] = low[crt] = level;
stk.push(crt);
for(auto nxt : edge[crt])
if(nxt != prv){
if(!viz[nxt]){
tarjan(nxt, crt, level+1);
low[crt] = min(low[crt], low[nxt]);
if(low[nxt] >= lvl[crt]){
cbc++;
while(!stk.empty() && stk.top() != nxt){
CBC[cbc].push_back(stk.top());
stk.pop();
}
stk.pop();
CBC[cbc].push_back(nxt);
CBC[cbc].push_back(crt);
}
}else{
low[crt] = min(low[crt], lvl[nxt]);
}
}
}
int main (){
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i=1, u, v; i<=m; i++){
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i=1; i<=n; i++)
if(!viz[i])
tarjan(i, 0, 1);
cout<<cbc<<"\n";
for(int i=1; i<=cbc; i++){
for(auto nod : CBC[i])
cout<<nod<<" ";
cout<<"\n";
}
return 0;
}
/**
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 5
7 8
**/