Cod sursa(job #1332488)

Utilizator MarianMMorosac George Marian MarianM Data 2 februarie 2015 03:23:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <list>
#include <iterator>
using namespace std;

#define DMAX 100002

int N, M, timeR, G_Tr = 1, v_put = 1, nrCTC;

struct Nod{
	int u, d, f;
	vector<int> Adj, AdjT;
} G[DMAX];

vector<int> V, CV;

void citire(){
	int i, x, y;

	scanf("%d %d", &N, &M);

	for ( i = 0; i < M; i++){
		scanf("%d %d\n", &x, &y);
		G[x].Adj.push_back(y);
		G[y].AdjT.push_back(x);
	}
}

void DFS(int root){
	int i, lg, chld;

	if (G_Tr) lg = G[root].Adj.size();
	else lg = G[root].AdjT.size();

	G[root].u++;
	G[root].d = ++timeR;

	for (i = 0; i < lg; i++){
		if(G_Tr) chld = G[root].Adj[i];
		else chld = G[root].AdjT[i];

		if (G[chld].u < G[root].u){
			DFS(chld);
		}
	}

	G[root].f = ++timeR;
	if(v_put) V.push_back(root);
}

int main(){
	int i;

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

	for (i = 1; i <= N; i++) {
		if (!G[i].u) {
			DFS(i);
		}
	}
			
	G_Tr = 0; v_put = 0;
	for (i = V.size() - 1; i >= 0; i--) {
		if (G[V[i]].u == 1){
			DFS(V[i]);
			nrCTC++;
		}
	}

	cout << nrCTC << '\n';

	v_put = 1;  CV = V;
	for (i = CV.size() - 1; i >= 0; i--)
		if (G[CV[i]].u == 2){
			V.clear();  
			DFS(CV[i]);
			for (int j = 0; j < V.size(); j++) 
				cout << V[j] << ' ';
			cout << '\n';
		}

	return 0;
}