Pagini recente » Cod sursa (job #1826068) | Cod sursa (job #2170482) | Cod sursa (job #1301749) | Cod sursa (job #1051956) | Cod sursa (job #3299570)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int niv[100001], h[100001];
vector<int> g[100001];
bool m[100001];
stack<int> s;
vector< vector<int> > comp;
void build(int nod){
m[nod] = 1;
s.push(nod);
for(const int &x : g[nod]){
if(m[x]){
h[nod] = min(h[nod], niv[x]); // muchie de intoarcere
continue;
}
niv[x] = h[x] = niv[nod] + 1;
build(x);
h[nod] = min(h[nod], h[x]);
if(h[x] >= niv[nod]){
// cout << "Este componenta de la " << nod << " ---> " << x << '\n';
comp.push_back({});
while(s.top() != x){
comp.back().push_back(s.top());
s.pop();
}
comp.back().push_back(s.top()); s.pop();
comp.back().push_back(nod);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
int n, m; in >> n >> m;
for(int i = 0; i < m; i++){
int a, b; in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
niv[1] = h[1] = 1;
build(1);
// cout << "h : ";
// for(int i = 1; i <= n; i++) cout << h[i] << " ";
// cout << '\n';
// cout << "niv : ";
// for(int i = 1; i <= n; i++) cout << niv[i] << " ";
// cout << '\n';
out << comp.size() << '\n';
for(const vector<int> &i : comp){
for(const int &x : i) out << x << " ";
out << '\n';
}
return 0;
}