Cod sursa(job #2602888)

Utilizator ShayTeodor Matei Shay Data 18 aprilie 2020 01:07:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>

constexpr int BUFFER_SIZE = 1 << 17;

char buffer[BUFFER_SIZE];
int pos = BUFFER_SIZE;
int num_components;

inline char next() {
	if (pos == BUFFER_SIZE) {
		fread(buffer, 1, BUFFER_SIZE, stdin);
		pos = 0;
	}
	
	return buffer[pos++];
}

inline int read() {
	int n = 0;
	char c = next();

	while (!('0' <= c && c <= '9')) {
		c = next();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + (c - '0');
		c = next();
	}

	return n;
}

inline void print(int n) {
	char snum[65];
	int i = 0;

	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while (n);

	--i;

	while (i >= 0) {
		putchar(snum[i--]);
	}

	putchar(' ');
}


void dfs(std::vector<int> *sol, std::vector<int> *adj, std::vector<int> &disc, std::vector<int> &low,
	std::stack<int> &stack, int src, int dad) {
		disc[src] = low[src] = disc[dad] + 1;
		stack.push(src);

		for (auto &it : adj[src]) {
			if (it != dad) {
				if (disc[it] == -1) {
					dfs(sol, adj, disc, low, stack, it, src);
					low[src] = std::min(low[src], low[it]);

					if (low[it] >= disc[src]) {
						int node;
						do {
							sol[num_components].emplace_back(node = stack.top());
							stack.pop();
						} while(it != node);

						sol[num_components++].emplace_back(src);
					}
				} else {
					low[src] = std::min(low[src], disc[it]);
				}
			}
		}
}

int main() {
    freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
    int n = read(), m = read();
    int x, y;

	std::vector<int> disc(n + 1, -1);
	std::vector<int> low(n + 1, 0);
	std::stack<int> stack;
	std::vector<int> *sol = new std::vector<int>[n + 1];
	std::vector<int> *adj = new std::vector<int>[n + 1];
	for (; m; --m) {
		x = read(), y = read();
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);

    }

	for (int i = 1 ; i <= n ; ++i) {
		if (disc[i] == -1) {
			dfs(sol, adj, disc, low, stack, i, 0);
		}
	}

	print(num_components);
	putchar('\n');
	for (int i = 0 ; i < num_components ; ++i, putchar('\n')) {
		for (const int &nod : sol[i]) {
			print(nod);
		}
	}

	delete [] adj;
	delete [] sol;
    return 0;
}