Pagini recente » Cod sursa (job #2720753) | Monitorul de evaluare | Monitorul de evaluare | tl | Cod sursa (job #3286744)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pii pair <int, int>
#define fr first
#define sc second
using namespace std;
string filename = "biconex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
////////////////////////////////////////////////////////////
const int NMAX = 1e5;
vt <int> adj[NMAX + 1];
stack <int> S;
bool viz[NMAX + 1];
int lvl[NMAX + 1];
int ll[NMAX + 1];
vt <vt <int>> comps;
void dfs(int node, int par){
viz[node] = 1;
S.push(node);
ll[node] = lvl[node] = lvl[par] + 1;
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]){
vt <int> aux;
while(S.top() != vec){
aux.pb(S.top());
S.pop();
}
aux.pb(S.top());
S.pop();
aux.pb(node);
comps.pb(aux);
}
}
}
}
}
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 << sz(comps) << '\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;
}