Cod sursa(job #2195773)

Utilizator flibiaVisanu Cristian flibia Data 17 aprilie 2018 13:08:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define fi first
#define se second 
#define N 100100

using namespace std;

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

int n, m, x, y, S, low[N], timp[N], cnt[N], timer;
vector <int> v[100100];
bitset <100100> viz;
vector <vector <int> > sol;
vector <pair <int, int> > edges;

void biconnect(pair <int, int> edge){
	vector <int> aux;
	while(edges.back() != edge){
		aux.push_back(edges.back().se);
		edges.pop_back();
	}
	aux.push_back(edges.back().se);
	aux.push_back(edges.back().fi);
	edges.pop_back();
	sol.push_back(aux);
	aux.clear();
}

void dfs(int dad, int from){
	viz[from] = 1;
	low[from] = timp[from] = ++timer;
	for(auto to : v[from]){
		if(to == dad)
			continue;
		if(!viz[to]){
			edges.push_back({from, to});
			dfs(from, to);
			if(from == S || timp[from] <= low[to]){
				cnt[from]++;
				biconnect({from, to});
			} else low[from] = min(low[from], low[to]);
		} else low[from] = min(low[from], timp[to]);
	}
}

int main(){
	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(!viz[i]){
			S = i;
			cnt[S] = -1;
			dfs(0, S);
		}	
	out << sol.size();
	for(int i = 0; i < sol.size(); i++){
		out << '\n';
		for(auto j : sol[i])
			out << j << ' ';
	}
	return 0;
}