Cod sursa(job #1451627)

Utilizator GilgodRobert B Gilgod Data 17 iunie 2015 21:47:09
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <sstream>

#define MIN(a,b) ((a)<(b))?(a):(b)

const char IN[] = "ctc.in", OUT[] = "ctc.out";
const int NMAX = 100001;

enum {WHITE, GREY, BLACK};

using namespace std;

list<int> G[NMAX];
int N, M;

inline void read_data() {
	freopen(IN, "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int src, dst;
		scanf("%d %d", &src, &dst);
		G[src].push_back(dst);
	}
	fclose(stdin);
}

int i = 0;
int lowlink[NMAX], index[NMAX];
stack<int> S;
bool inS[NMAX];

int ctcCount;
ostringstream sout;

void Tarjan(int node) {
	index[node] = lowlink[node] = ++i;
	S.push(node);
	inS[node] = true;
	for (const int n : G[node]) {
		if (index[n] == 0 || inS[n]) {
			if (!index[n]) Tarjan(n);
			lowlink[node] = MIN(lowlink[node], lowlink[n]);
		}
	}
	if (index[node] == lowlink[node]) {
		++ctcCount;
		int v;
		do {
			v = S.top(); S.pop();
			sout << v << " ";
		} while (v != node);
		sout << endl;
	}
}

int main() {
	read_data();
	for (int node = 1; node <= N; ++node) {
		if (!index[node]) Tarjan(node);
	}
	fprintf(fopen(OUT, "w"), "%d\n%s", ctcCount, sout.str().c_str());
	return 0;
}