Cod sursa(job #3230848)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 22 mai 2024 23:53:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5+10;
int n,m,numar;
vector<vector<int>> mat(nmax),ans(nmax);
vector<int> visited(nmax),nivel(nmax),nma(nmax);
stack<int> s;
void read_input(){
	fin >> n >> m;
	int nod_1,nod_2;
	for(int i = 1; i <=m; i++){
		fin >> nod_1 >> nod_2;
		mat[nod_1].push_back(nod_2);
		mat[nod_2].push_back(nod_1);
	}
};
void dfs(int nod,int tata,int &numar){
	visited[nod] = 1;
	nivel[nod] = nivel[tata]+1;
	nma[nod] = nivel[nod];
	s.push(nod);
	for(auto nod_aux : mat[nod]){
		if(nod_aux != tata){
			if(visited[nod_aux]){
				nma[nod] = min(nma[nod],nivel[nod_aux]);
			}else{
				dfs(nod_aux,nod,numar);
				nma[nod] = min(nma[nod],nma[nod_aux]);
				if(nivel[nod] <= nma[nod_aux]){
					numar++;
					while(!s.empty() && s.top() != nod_aux){
						ans[numar].push_back(s.top());
						s.pop();
					};
					ans[numar].push_back(nod_aux);
					s.pop();
					ans[numar].push_back(nod);
				}
			}
		}
	}
}
int main(){
	read_input();
	numar = 0;
	dfs(1,0,numar);
	fout << numar << '\n';
	for(int i = 1; i <=numar; i++,fout << '\n'){
		for(auto x : ans[i]){
			fout << x << " ";
		}
	};
	return 0;
}