Cod sursa(job #2709658)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 20 februarie 2021 21:06:41
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

stack <pair <int, int>> st;

vector <vector <int>> bcc;
vector <int> gr[100001];

int tin[100001], low[10001];
int N, M, timer;

void Read(){
	f >> N >> M;
	while(M--){
		int x, y;
		f >> x >> y;
		gr[x].emplace_back(y);
		gr[y].emplace_back(x);
	}
}

void find_bcc(int x, int y){
	vector <int> con;
	int tx, ty;

	do{
		tx = st.top().first, ty = st.top().second;
		st.pop();
		con.emplace_back(tx), con.emplace_back(ty);
	}while(tx != x || ty != y);
	bcc.emplace_back(con);
}

void dfs(int v, int p, int timer){
	tin[v] = low[v] = timer;

	for(int to : gr[v]){
		if(to == p) continue;

		if(tin[to] == -1){
			st.push({v, to});
			dfs(to, v, timer + 1);
			low[v] = min(low[v], low[to]);

			if(low[to] >= tin[v])
				find_bcc(v, to);
		}
		else low[v] = min(low[v], tin[to]);
	}
}


void Solve(){
	timer = 0;
	for(int i = 1;i <= N;i++)
		tin[i] = low[i] = -1;

	dfs(1, 0, 0);
}

void Print_bcc(){
	g << bcc.size() << "\n";
	for(int i = 0;i < (int)bcc.size();i++){
		sort(bcc[i].begin(), bcc[i].end());
        bcc[i].erase(unique(bcc[i].begin(), bcc[i].end()), bcc[i].end());
		for(int x : bcc[i])
			g << x << " ";
		g << "\n";
	}
}


int main(){
	Read();
	Solve();
	Print_bcc();
}