Cod sursa(job #1222650)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 23 august 2014 22:43:05
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 100010

vector<int> Gr[MAX];
stack<int> S;
bool Visited[MAX];
vector<vector<int> > Ctc;
int N, M, Index[MAX], LowLink[MAX], K, Step;

void DFS(int X) {
	int Y;
	K++;
	Index[X] = K;
	LowLink[X] = K;
	K++;
	S.push(X);
	Visited[X] = Step;
	for (int i = 0; i < Gr[X].size(); i++) {
		Y = Gr[X][i];
		if (Index[Y] == 0) {
			DFS(Y);
			LowLink[X] = min(LowLink[X], LowLink[Y]);
		} else
		if (Visited[Y] == Step) {
			LowLink[X] = min(LowLink[X], Index[Y]);
		}
	}
	
	if (LowLink[X] == Index[X]) {
		Ctc.resize(Ctc.size()+1);
		do {
			Y = S.top();
			Ctc[Ctc.size()-1].push_back(Y);
			S.pop();
		} while (X != Y);
	}
}

int main() {
	int X, Y;

	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &X, &Y);
		Gr[X].push_back(Y);
	}
	
	for (int i = 1; i <= N; i++) {
		Step++;
		if (Index[i] == 0) {
			DFS(i);
		}
	}
	
	printf("%d\n", Ctc.size());
	for (int i = 0; i < Ctc.size(); i++) {
		for (int j = 0; j < Ctc[i].size(); j++) {
			printf("%d ", Ctc[i][j]);
		}
		printf("\n");
	}

	return 0;
}