Cod sursa(job #1686078)

Utilizator aimrdlAndrei mrdl aimrdl Data 12 aprilie 2016 01:26:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <string.h>

using namespace std;

int n, m;
vector < vector <int> > G;
vector < vector <int> > sol;
stack <int> S;
int cnt;
int idx[100005], lowlink[100005];
bool inStack[100005];

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

	G.resize(n + 1);

	int x, y;
	for (int i = 0; i < m; ++i) {
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
	}
}

void dfsTarjan (int i) {
	idx[i] = cnt;
	lowlink[i] = cnt;
	++cnt;
	S.push(i);
	inStack[i] = true;

	vector <int>::iterator it;
	for (it = G[i].begin(); it != G[i].end(); ++it) {
		if (idx[*it] == -1) {
			dfsTarjan(*it);
			lowlink[i] = min(lowlink[i], lowlink[*it]);
		} else if (inStack[*it] == true) {
			lowlink[i] = min(lowlink[i], idx[*it]);
		}
	}

	if (idx[i] == lowlink[i]) {
		sol.push_back(vector<int> (0));
		int x;
		do {
			x = S.top();
			inStack[x] = false;
			sol[sol.size() - 1].push_back(x);
			S.pop();
		} while (x != i);
	}
}

void tarjan () {
	for (int i = 1; i <= n; ++i) {
		if (idx[i] == -1) {
			dfsTarjan(i);
		}
	}
}

int main (void) {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	memset(idx, -1, sizeof(idx));
	memset(lowlink, 9999999, sizeof(lowlink));

	read();

	tarjan();

	printf("%lu\n", sol.size());

	vector< vector <int> >::iterator it;
	for (it = sol.begin(); it != sol.end(); ++it) {
		vector <int>::iterator jt;
		for (jt = it->begin(); jt != it->end(); ++jt) {
			printf("%d ", *jt);
		}
		printf("\n");
	}

	return 0;
}