Cod sursa(job #3223301)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 12 aprilie 2024 22:45:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>
#include <algorithm>

int32_t min(int32_t x, int32_t y) {
	return (x < y) ? x : y;
}

const int32_t MAX_N = 100000;
const int32_t MAX_M = 200000;

struct Edge {
	int32_t x, y;
};

std::vector<int32_t> adj[MAX_N];
int32_t depths[MAX_N], low[MAX_N];

Edge stack[MAX_N]; int32_t top;
std::vector<int32_t> comps[MAX_N]; int32_t count;

void DFS(int32_t node, int32_t prev, int32_t depth) {
	depths[node] = depth;
	low[node] = depth;

	for(int32_t next : adj[node]) {
		if(next == prev)
			continue;
		
		if(depths[next] == -1) {
			stack[top++] = { node, next };
			DFS(next, node, depth + 1);
			low[node] = min(low[node], low[next]);

			if(low[next] >= depth) {
				do {
					comps[count].push_back(stack[top - 1].x);
					comps[count].push_back(stack[top - 1].y);
					--top;
				} while(stack[top].x != node || stack[top].y != next);

				std::sort(comps[count].begin(), comps[count].end());
				comps[count].erase(std::unique(comps[count].begin(), comps[count].end()), comps[count].end());

				++count;
			}
		} else {
			low[node] = min(low[node], depths[next]);
		}
	}
}

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

	int32_t n, m;
	fin >> n >> m;

	for(int32_t i = 0; i != m; ++i) {
		int32_t x, y;
		fin >> x >> y;
		--x; --y;

		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for(int32_t i = 0; i != n; ++i)
		depths[i] = -1;
	
	DFS(0, -1, 0);

	fout << count << '\n';
	for(int32_t i = 0; i != count; ++i) {
		for(int32_t node : comps[i])
			fout << (node + 1) << ' ';
		fout << '\n';
	}

	fin.close();
	fout.close();

	return 0;
}