Cod sursa(job #1910277)

Utilizator lflorin29Florin Laiu lflorin29 Data 7 martie 2017 16:16:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

const int nMax = 1e5 + 2;

int n, m, low[nMax], tin[nMax], id;
vector<int>g[nMax];
stack<int>st;
bool in_st[nMax];
vector<vector<int>>comp;

void citire() {
	scanf("%d%d", &n, &m);

	for (int i = 1, a, b; i <= m; ++i) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
	}

}

void add_comp(int nod) {
	comp.push_back(vector<int>());
	int bag = -1;

	do {
		bag = st.top(), st.pop();
		in_st[bag] = false;
		comp.back().push_back(bag);
	}
	while (bag != nod);
}
void dfs(int nod) {
	++id;
	st.push(nod);
	in_st[nod] = true;
	low[nod] = id;
	tin[nod] = id;

	for (const auto &itr : g[nod]) {
		if (!low[itr]) {
			dfs(itr);
			low[nod] = min(low[nod], low[itr]);
		}
		else {
			if (in_st[itr])
				low[nod] = min(low[nod], tin[itr]);
		}

	}

	if (low[nod] == tin[nod]) {
		add_comp(nod);
	}
}

void PrintComps() {
	printf("%d\n", comp.size());

	for (auto &itr : comp) {
		sort(itr.begin(), itr.end());
		itr.resize(unique(itr.begin(), itr.end()) - itr.begin());

		for (const auto &i : itr)
			printf("%d ", i);

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

	citire();

	for (int i = 1; i <= n; ++i)
		if (!tin[i])dfs(i);
	PrintComps();
	return 0;

}