Cod sursa(job #2279183)

Utilizator marcudanfDaniel Marcu marcudanf Data 9 noiembrie 2018 00:48:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>

const int NMAX = 1e5 + 5;

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector < int > g[NMAX];
vector < vector < int > > ans;
vector < int > s;

int viz[NMAX], h[NMAX], low[NMAX];

int n, m;
int len;

void dfs(int nod, int tata){
	h[nod] = low[nod] = h[tata] + 1;
	viz[nod] = 1;
	s.push_back(nod);
	for(int i : g[nod])
		if(i != tata){
			if(viz[i])
				low[nod] = min(low[nod], h[i]);
			else{
				dfs(i, nod);
				low[nod] = min(low[nod], low[i]);
				if(low[i] >= h[nod]){
					ans.emplace_back();
					ans.back().push_back(nod);
					while(s.back() != i){
						ans.back().push_back(s.back());
						s.pop_back();
					}
					s.pop_back();
					ans.back().push_back(i);
					len++;
				}
			}
		}
}

int main(){
	fin >> n >> m;
	while(m--){
		int a, b;
		fin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 0);
	fout << len << '\n';
	for(auto &i : ans){
		for(int a : i)
			fout << a << ' ';
		fout << '\n';
	}
	return 0;
}