Cod sursa(job #1222629)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 23 august 2014 21:52:15
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100010

vector<int> Gr[MAX], Tr[MAX];
vector<vector<int> > Ctc;
int N, M, GrViz[MAX], TrViz[MAX], K = 1;

void GrDfs(int X) {
	GrViz[X] = K;
	for (int i = 0; i < Gr[X].size(); i++) {
		if (GrViz[Gr[X][i]] < K) {
			GrDfs(Gr[X][i]);
		}
	}
}

void TrDfs(int X) {
	TrViz[X] = K;
	if (GrViz[X] == K) {
		Ctc[Ctc.size()-1].push_back(X);
		GrViz[X] = N+1;
		TrViz[X] = N+1;
	}
	for (int i = 0; i < Tr[X].size(); i++) {
		if (TrViz[Tr[X][i]] < K) {
			TrDfs(Tr[X][i]);
		}
	}
}

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);
		Tr[Y].push_back(X);
	}
	
	for (int i = 1; i <= N; i++) {
		if (GrViz[i] < K) {
			GrDfs(i);
			Ctc.resize(Ctc.size() + 1);
			TrDfs(i);
			K++;
		}
	}
	
	cout << Ctc.size() << endl;
	for (int i = 0; i < Ctc.size(); i++) {
		for (int j = 0; j < Ctc[i].size(); j++) {
			cout << Ctc[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}