Cod sursa(job #1816035)

Utilizator msciSergiu Marin msci Data 26 noiembrie 2016 00:22:58
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <functional>
#include <queue>
#include <stack>
using namespace std;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3f;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (y > x) x = y; }

struct Node {
	int num;
	int low;
	int comp;
	vector<int> adj;
	Node() {
		num = -1;
		comp = -1;
	}
};

const int NMAX = 100005;

int N, M;
Node V[NMAX];
vector<int> cc[NMAX];

stack<int> s;
int num = 0, C = 0;

void tarjanSCC(int u) {
	V[u].num = num++;
	V[u].low = V[u].num;
	s.push(u);
	for (auto &e : V[u].adj) {
		if (V[e].num == -1) {
			tarjanSCC(e);
			V[u].low = min(V[u].low, V[e].low);
		} else if (V[e].comp == -1) {
			V[u].low = min(V[u].low, V[e].num);
		}
	}	
	if (V[u].num == V[u].low) {
		int v;
		do {
			v = s.top();
			cc[C].push_back(v);
			s.pop();
			V[v].comp = C;
		} while (v != u);
		C++;
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		V[x].adj.push_back(y);
	}
	for (int i = 1; i <= N; i++) {
		if (V[i].num < 0) {
			tarjanSCC(i);
		}
	}
	cout << C << endl;
	for (int i = 0; i < C; i++) {
		for (auto &j : cc[i]) {
			cout << j << " ";
		}
		cout << endl;
	}
}