Pagini recente » Cod sursa (job #2719882) | Cod sursa (job #212395) | Cod sursa (job #579346) | infoarena - te ajutam sa devii olimpic! | Cod sursa (job #2871027)
/*
__
_.--"" |
.----. _.-' |/\| |.--.
| |__.-' _________| |_) _______________
| .-""-.""""" ___, `----'")) __ .-""-.""""--._
'-' ,--. ` |Cezar| .---. |:.| ' ,--. ` _`.
( ( ) ) __| 7 |__\\|// _..-- \/ ( ( ) )--._".-.
. `--' ;\__________________..--------. `--' ;--------'
`-..-' `-..-'
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int N = 1e5 + 5;
vector <int> v[N];
int t[N],t_min[N];
int timp = 1,nr_componente;
stack<int>s;
vector<int>rez[N];
ofstream out("biconex.out");
void dfs(int x, int tata){
// cout<<x<<' ';
s.push(x);
t[x] = t_min[x] = timp++;
for(auto y:v[x]){
if(t[y] == 0){
dfs(y,x);
t_min[x] = min(t_min[x],t_min[y]);
if(t_min[y]>=t[x]){
while(s.top()!=y){
rez[nr_componente].push_back(s.top());
s.pop();
}
s.pop();
rez[nr_componente].push_back(y);
rez[nr_componente].push_back(x);
nr_componente++;
}
}
else if(y!=tata){
t_min[x] = min(t_min[x],t[y]);
}
}
}
int main() {
ifstream in("biconex.in");
int n,m,x,y;
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(t[i] == 0)
dfs(i,0);
}
out<<nr_componente<<'\n';
for(int i=0;i<nr_componente;i++){
for(auto y:rez[i])
out<<y<<' ';
out<<'\n';
}
return 0;
}