Cod sursa(job #2175379)

Utilizator flibiaVisanu Cristian flibia Data 16 martie 2018 16:56:11
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define N 100100
#define fi first
#define se second

using namespace std;

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

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

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

void dfs(int dad, int from){
	viz[from] = 1;
	timp[from] = low[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]) || from == S){
				cnt[from]++;
				biconex({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, i);
		}
	out << sol.size();
	for(auto V : sol){
		out << '\n';
		for(auto i : V)
			out << i << ' ';
	}
	return 0;
}