Cod sursa(job #1425111)

Utilizator GilgodRobert B Gilgod Data 26 aprilie 2015 18:07:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <sstream>

#define NMAX 100001
#define min(a,b) ((a) < (b))?(a):(b)

using namespace std;

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

vector<int> G[NMAX];
int lowlink[NMAX];
int index[NMAX];
int searchTime = 0;
int N;
bool inStack[NMAX];
int NRS = 0;
ostringstream out;

inline void readData() {
	FILE *fin = freopen(IN, "r", stdin);
	if (!fin) return;
	int M;
	scanf(" %d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int s, d; 
		scanf(" %d%d", &s, &d);
		G[s].push_back(d);
	}
	fclose(stdin);
}
stack<int> S;
void tarjan(int nod) {
	index[nod] = lowlink[nod] = ++searchTime;
	S.push(nod);
	inStack[nod] |= 1;
 	for (const int n : G[nod]) {
		if (index[n] == 0) {
			tarjan(n);
			lowlink[nod] = min(lowlink[nod], lowlink[n]);
		}
		else if (inStack[n]) {
			lowlink[nod] = min(lowlink[nod], lowlink[n]);
		}
	}
	if (lowlink[nod] == index[nod]) {
		//root
		int u;
 		do {
			u = S.top(); S.pop();
			inStack[u] &= 0;
			out << u << " ";
		} while (u != nod);
		NRS++;
		out << endl;
	}
}

int main() {
	readData();
	freopen(OUT, "w", stdout);
	for (int i = 1; i <= N; i++)
		if (index[i] == 0) tarjan(i);
	printf("%d\n", NRS);
	cout << out.str();
	fclose(stdout);
}