Cod sursa(job #2434131)

Utilizator ShayTeodor Matei Shay Data 30 iunie 2019 17:46:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <string.h>

inline int next_int() {
	int n = 0;
	char c = getchar_unlocked();
	
	while (!('0' <= c && c <= '9')) {
		c = getchar_unlocked();
	}
	
	while ('0' <= c && c <= '9') {
		n = n * 10 + c - '0';
		c = getchar_unlocked();
	
	}

	return n;
}

void tarjan(std::vector<std::vector<int>> &scc , const std::vector<int> *adj, const int src, int disc[],
		int low[], std::vector<bool> &is_on_stack, std::stack<int> &s) {
	static int time = 0;
	disc[src] = low[src] = ++time;
	s.push(src);
	is_on_stack[src] = true;

	for (auto it = adj[src].begin() ; it != adj[src].end(); ++it) {
		if (disc[*it] == -1) {
			tarjan(scc, adj, *it, disc, low, is_on_stack, s);
			low[src] = std::min(low[src], low[*it]);
		} else if (is_on_stack[*it] == true) {
			low[src] = std::min(low[src], low[*it]);
		}
	}

	if (disc[src] == low[src]) {
		std::vector<int> comp;
		int node;
		do {
			comp.push_back(node = s.top());
			s.pop();
			is_on_stack[node] = false;
		} while(node != src);

		scc.push_back(comp);
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	int n, m, src, dest;
	n = next_int();
	m = next_int();
	std::vector<std::vector<int>> scc;
	std::vector<int> adj[n];
	int disc[n], low[n];
	std::vector<bool> is_on_stack(n, false);
	std::stack<int> s;
	memset(disc, -1, sizeof(disc));
	memset(low, 0, sizeof(low));
		
	for (; m ; --m) {
		src = next_int();
		dest = next_int();
		adj[src - 1].push_back(dest - 1);
	}

	for (int i = 0 ; i < n ; ++i) {
		if (disc[i] == -1) {
			tarjan(scc, adj, i, disc, low, is_on_stack, s);
		}
	}

	printf("%ld\n", scc.size());
	for (int i = 0 ; i < scc.size() ; ++i) {
		for (int j = 0 ; j < scc[i].size() ; ++j) {
			printf("%d ", scc[i][j] + 1);
		}

		printf("\n");
	}

	return 0;
}