Cod sursa(job #2717524)

Utilizator M4theuSMatheus Henrique de Sousa Silva M4theuS Data 7 martie 2021 15:45:47
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

#define ll long long
#define pb push_back
#define sz(x) int(x.size())

typedef pair<int,int>ii;
typedef vector<int> vi;

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
const int mxn=1e5+5;
int n,m,t,in[mxn],low[mxn];
vector<vi>ans;
vi g[mxn];
stack<int>st;
void dfs(int i,int p){
	in[i]=low[i]=++t;
	st.push(i);
	for(int j:g[i])if(j!=p){
		if(in[j])low[i]=min(low[i],in[j]);
		else{
			dfs(j,i);
			low[i]=min(low[i],low[j]);
			if(low[j]>=in[i]){
				vi aux;
				while(aux.empty() || aux.back()!=j){
					aux.pb(st.top());
					st.pop();
				}	
				aux.pb(i);
				ans.pb(aux);
			}
		}
	}
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//setIO("sort");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			dfs(i,0);
		}
	}
	cout<<sz(ans)<<"\n";
	for(vi i:ans){
		for(int j:i)cout<<j<<" ";
		cout<<"\n";
	}
	return 0;
}