Cod sursa(job #3222882)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 11 aprilie 2024 20:03:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include<fstream>
#include<vector>
#include<set>
#include<stack>
#include<set>
#include<algorithm>

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

std::vector<std::vector<int> > G;
std::vector<int> nivel, viz, nma;
std::set<int> puncteCritice;
std::vector<std::pair<int, int> > punti;
std::vector<std::set<int> > componente;
std::stack<int> dfsOrder;
int task, n, m;

void DFS(int start, int tata) {
	viz[start] = 1;
	dfsOrder.push(start);
	nivel[start] = nivel[tata] + 1;
	nma[start] = nivel[start];
	int cnt = 0;


	for(const int& x : G[start])
		if (x != tata) {
			if (viz[x]) {
				if (nma[start] > nivel[x])
					nma[start] = nivel[x];
			}
			else {
				DFS(x, start);
				++cnt;
				if (nma[start] > nma[x])
					nma[start] = nma[x];

				if (nma[x] >= nivel[start] and start != 1)
					puncteCritice.insert(start);

				if (nma[x] > nivel[start])
					punti.push_back(std::make_pair(x, start));

				if (nma[x] >= nivel[start]) {
					std::set<int> comp;
					while (dfsOrder.top() != x) {
						comp.insert(dfsOrder.top());
						dfsOrder.pop();
					}
					comp.insert(x);
					comp.insert(start);
					dfsOrder.pop();
					componente.push_back(comp);
				}
			}
		}

	if (start == 1 and cnt > 1)
		puncteCritice.insert(1);
}

int main() {;
	fin >> n >> m;

	G.resize(n + 1);
	nivel.resize(n + 1);
	nma.resize(n + 1);
	viz.resize(n + 1);

	int x, y;

	for (; m; --m) {
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	DFS(1, 0);
	
		fout << componente.size() << '\n';
		for (const std::set<int>& S : componente) {
			for (const int& x : S)
				fout << x << ' ';
			fout << '\n';
		}
}