Cod sursa(job #2139096)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 22 februarie 2018 02:38:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100010;

int N, M;
int currTime;
int discoverTime[NMAX], lowLink[NMAX];
bool inStack[NMAX];
vector<int> G[NMAX];
vector<vector<int>> SCC;
stack<int> V;

void dfsTarjan(int node) {
	V.push(node);
	inStack[node] = 1;
	discoverTime[node] = lowLink[node] = currTime++;
	for (int it: G[node]) {
		if (discoverTime[it] == -1) {
			dfsTarjan(it);
			lowLink[node] = min(lowLink[node], lowLink[it]);
		} else if (inStack[it])
			lowLink[node] = min(lowLink[node], discoverTime[it]);
	}
	if (lowLink[node] == discoverTime[node]) {
		int curr;
		vector<int> currScc;
		do {
			curr = V.top();
			V.pop();
			inStack[curr] = 0;
			currScc.push_back(curr);
		} while (curr != node);
		SCC.push_back(currScc);
	}
}

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

	memset(discoverTime, -1, sizeof discoverTime);

	cin >> N >> M;
	while (M--) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; ++i)
		if (discoverTime[i] == -1)
			dfsTarjan(i);

	cout << SCC.size() << '\n';
	for (auto i: SCC) {
		for (auto j: i)
			cout << j << ' ';
		cout << '\n';
	}

	return 0;
}