Cod sursa(job #3293885)

Utilizator mihai21681Maricutu Mihai Alexandru mihai21681 Data 12 aprilie 2025 21:21:28
Problema Componente biconexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
// biconexe.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int, int> PI;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, dfn[1001], low[1001];
vector<int> G[1001];
vector<vector<int>> C;
stack<PI> S;
void DFS(int n, int fn, int nr) {
	dfn[n] = low[n] = nr;
	for (int i : G[n]) {
		if (i == fn) continue;
		if (dfn[i] == -1) {
			S.push({ n, i });
			DFS(i, n, nr + 1);
			low[n] = min(low[n], low[i]);
			if (low[i] >= dfn[n]) {
				vector<int> comp; int tx, ty;
				do {
					tx = S.top().first, ty = S.top().second;
					S.pop();
					comp.push_back(tx); comp.push_back(ty);
				} while (tx != n && ty != i);
				C.push_back(comp);
			}
		}
		else low[n] = min(low[n], dfn[i]);
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	fill(dfn + 1, dfn + 1 + n, -1);
	fill(low + 1, low + 1 + n, -1);
	DFS(1, 0, 0);
	cout << C.size() << '\n';
	for (vector<int> comp : C) {
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		for (int i : comp)
			cout << i << ' ';
		cout << '\n';
	}
		
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file