Cod sursa(job #1899058)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 2 martie 2017 15:00:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <vector>

using namespace std;
vector<int> *G, *Gt, *C;
bool *viz, *A;
int *L, sp;

void dfs(int u)
{
	if (!viz[u]) {
		viz[u] = true;
		for (unsigned int i = 0; i < G[u].size(); ++i) {
			dfs(G[u][i]);
		}
		L[++sp] = u;
	}
}

void assign(int u, int root)
{
	if (!A[u]) {
		A[u] = 1;
		C[root].push_back(u);
		for (unsigned int i = 0; i < Gt[u].size(); ++i) {
			assign(Gt[u][i], root);
		}
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("ctc.in", "r");
	fout = fopen("ctc.out", "w");
	
	int N, M;
	fscanf(fin, "%d%d", &N, &M);
	
	G = new vector<int>[N+1]();
	Gt = new vector<int>[N+1]();
	for (int i = 0; i < M; ++i) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		G[x].push_back(y);
		Gt[y].push_back(x);
	}
	
	L = new int[N+1]();
	A = new bool[N+1]();
	viz = new bool[N+1]();
	C = new vector<int>[N+1]();
	
	for (int i = 1; i <= N; ++i) {
		dfs(i);
	}
	for (int i = N; i >= 1; --i) {
		assign(L[i], L[i]);
	}
	
	int nc = 0;
	for (int i = 1; i <= N; ++i) {
		if (C[i].size()) {
			++nc;
		}
	}
	
	fprintf(fout, "%d\n", nc);
	for (int i = 1; i <= N; ++i) {
		if (C[i].size()) {
			for (unsigned int u = 0; u < C[i].size(); ++u) {
				fprintf(fout, "%d ", C[i][u]);
			}
			fprintf(fout, "\n");
		}
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}