Cod sursa(job #2759968)

Utilizator MateGMGozner Mate MateGM Data 21 iunie 2021 18:50:38
Problema Componente biconexe Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.24 kb
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <fstream>

using namespace std;

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

struct elek {
	int kezdop;
	int vegp;
};

void beolvas(vector<vector<int>>& graf, int m);
void BIC(vector<vector<int>>& graf, int n);
void DFS_BIC(vector<vector<int>>& graf, int n, int v, int szulo, int& ido, stack<elek>& verem, vector<int>& belep, vector<int>& low, vector<int>& elvagoCsucsok,
	vector<vector<elek>>& komponensek, vector<elek>& hidak, int& komponens);

int main()
{
	int n, m;
	be >> n >> m;
	vector<vector<int>> graf(n);
	beolvas(graf, m);
	BIC(graf, n);
}

void beolvas(vector<vector<int>>& graf, int m) {
	for (int i = 0; i < m; i++) {
		int x, y;
		be >> x >> y;
		graf[x - 1].push_back(y - 1);
		graf[y - 1].push_back(x - 1);
	}
}

void BIC(vector<vector<int>>& graf, int n) {
	stack<elek> verem;
	vector<int> belep(n, -1);
	vector<int> low(n);
	vector<int> elvagoCsucsok;
	vector<vector<elek>> komponensek;
	vector<elek> hidak;
	int szulo = 0, ido = 0, komponens = 0;

	for (int i = 0; i < n; ++i) {
		if (belep[i] == -1) {
			DFS_BIC(graf, n, i, szulo, ido, verem, belep, low, elvagoCsucsok, komponensek, hidak, komponens);
		}
	}

	/*ki << "Hidak szama : " << hidak.size() << endl;

	for (int i = 0; i < hidak.size(); ++i) {
		ki << hidak[i].kezdop + 1 << " " << hidak[i].vegp + 1 << endl;
	}


	ki << "Elvago csucsok szama : " << elvagoCsucsok.size() << endl;
	for (int i = 0; i < elvagoCsucsok.size(); ++i) {
		ki << elvagoCsucsok[i] + 1 << endl;
	}*/

	ki /* << "Ketszeresen osszefuggo komponensek szama : " */<< komponensek.size() << "\n";
	for (int i = 0; i < komponensek.size(); ++i) {
		//ki << i + 1 << "\n" /* << ". komponens" << endl*/;
		for (int j = komponensek[i].size() - 1; j >= 0; --j)
			if (komponensek[i].size() > 1) ki << komponensek[i][j].kezdop + 1 << " ";
			else ki << komponensek[i][j].kezdop + 1 << " " << komponensek[i][j].vegp + 1;
		ki << "\n";
	}
}

void DFS_BIC(vector<vector<int>>& graf, int n, int v, int szulo, int& ido, stack<elek>& verem, vector<int>& belep, vector<int>& low, vector<int>& elvagoCsucsok,
	vector<vector<elek>>& komponensek, vector<elek>& hidak, int& komponens)
{
	++ido;
	belep[v] = ido;
	low[v] = ido;
	int gyerek = 0;
	bool elvagoCsucs = false;
	elek el;

	for (int i : graf[v]) {
		if (belep[i] == -1) {
			el.kezdop = v;
			el.vegp = i;
			verem.push(el);
			gyerek++;

			DFS_BIC(graf, n, i, v, ido, verem, belep, low, elvagoCsucsok, komponensek, hidak, komponens);

			low[v] = min(low[v], low[i]);
			if (low[i] >= belep[i]) {
				hidak.push_back(el);
			}

			if (low[i] >= belep[v]) {
				elvagoCsucs = true;
				komponens++;
				komponensek.resize(komponens);
				while ((verem.top().kezdop != v) && (verem.top().vegp != i)) {
					komponensek[komponens - 1].push_back(verem.top());
					verem.pop();
				}
				komponensek[komponens - 1].push_back(verem.top());
				verem.pop();
			}
		}
		else if ((i != szulo) && (belep[i] < belep[v])) {
			el.kezdop = v;
			el.vegp = i;
			verem.push(el);
			low[v] = min(low[v], belep[i]);
		}
	}
	if ((szulo != -1 && elvagoCsucs) || (szulo = -1 && gyerek > 1))
		elvagoCsucsok.push_back(v);
}