Cod sursa(job #1259741)

Utilizator veleanduAlex Velea veleandu Data 10 noiembrie 2014 15:28:34
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
//Problem plan from Infoarena
// "We are drowning in information and starved for knowledge."
#include <cassert>
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define int64 long long

const int inf = 0x3f3f3f3f, kMaxN = 100005;

ifstream in("ctc.in");
ofstream out("ctc.out");

bool viz[kMaxN];
int ord[kMaxN];

vector<int> vertex[kMaxN], vertex_back[kMaxN];
vector<int> ctc_el[kMaxN]; int ctc[kMaxN];
vector<int> ctc_vertex[kMaxN]; int ctc_in[kMaxN];

void df_1(int nod) {
	if (viz[nod])
		return ;
	viz[nod] = true;
	ord[++ord[0]] = nod;
	for (int it : vertex[nod])
		df_1(it);
	return ;
}

void df_2 (int nod) {
	if (viz[nod])
		return ;
	viz[nod] = true;
	ctc[nod] = ctc[0];
	for (int itr : vertex_back[nod])
		df_2(itr);
	return ;
}

int main() {
	int n, m;
	in >> n >> m;

	for (int i = 1; i <= m; ++i) {
		int a, b;
		in >> a >> b;
		vertex[a].push_back(b);
		vertex_back[b].push_back(a);
	}
	
	for (int i = 1; i <= n; ++i)
		df_1(i);
	for (int i = 1; i <= n; ++i)
		viz[i] = 0;

	for (int i = 1; i <= n; ++i)
		if (not viz[ord[i]]) {
			++ctc[0];
			df_2(ord[i]);
		}

	for (int i = 1; i <= n; ++i) {
		ctc_el[ctc[i]].push_back(i);
		for (int it : vertex[i])
			if (ctc[i] != ctc[it]) {
				ctc_vertex[ctc[i]].push_back(ctc[it]);
				ctc_in[ctc[it]]++;
			}
	}

	out << ctc[0] << '\n';
	for (int i = 1; i <= int(ctc[0]); ++i, out << '\n')
		for (int itr : ctc_el[i])
			out << itr << ' ';
	return 0;
}