Cod sursa(job #2078107)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 28 noiembrie 2017 22:04:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

int N, M;
vector<int> graph[NMAX], grapht[NMAX], comp[NMAX];
bitset<NMAX> used;
stack<int> st;
int components;

void read() {
	scanf("%d %d ", &N, &M);

	for (int i = 1; i <= M; i++) {
		int x, y;
		scanf("%d %d ", &x, &y);
		graph[x].push_back(y);
		grapht[y].push_back(x);
	}
}

void dfs(int node) {
	used[node] = 1;
	for (auto it: graph[node]) {
		if (!used[it])
			dfs(it);
	}
	st.push(node);
}

void dfst(int node, int first) {
	comp[first].push_back(node);
	used[node] = 1;
	for (auto it: grapht[node]) {
		if(!used[it])
			dfst(it, first);
	}
}

void kosaraju() {
	for (int i = 1; i <= N; i++) {
		if(!used[i]) dfs(i);
	}

	used.reset();

	for(; !st.empty(); st.pop()) {
		int node = st.top();

		if(!used[node]) {
			++components;
			dfst(node, node);
		}
	}
}

void print() {
	printf("%d\n", components);
	for (int i = 1; i <= N; i++) {
		if(!comp[i].size()) continue;

		for	(auto it: comp[i])
			printf("%d ", it);
		printf("\n");
	}
}

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

	read();
	kosaraju();
	print();

	return 0;
}