Pagini recente » Cod sursa (job #487882) | Cod sursa (job #3293943)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
string filename = "biconex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int NMAX = 1e5;
vt <int> adj[NMAX + 1];
bool viz[NMAX + 1];
int lvl[NMAX + 1];
int ll[NMAX + 1];
stack <int> S;
int nrComps = 0;
vt <vt <int>> comps;
void dfs(int node, int par){
lvl[node] = ll[node] = lvl[par] + 1;
viz[node] = 1;
S.push(node);
for(int vec : adj[node]){
if(vec != par){
if(viz[vec]){
ll[node] = min(ll[node], lvl[vec]);
}else{
dfs(vec, node);
ll[node] = min(ll[node], ll[vec]);
if(ll[vec] >= lvl[node]){
nrComps++;
vt <int> comp;
while(S.top() != vec){
comp.pb(S.top());
S.pop();
}
comp.pb(S.top());
S.pop();
comp.pb(node);
comps.pb(comp);
}
}
}
}
}
void solve(){
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b;
fin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1, 0);
fout << nrComps << '\n';
for(vt <int> comp : comps){
for(int x : comp){
fout << x << ' ';
}
fout << '\n';
}
}
int main(){
int T;
//fin >> T;
T = 1;
while(T--){
solve();
}
return 0;
}