Cod sursa(job #1132557)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 3 martie 2014 17:06:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <vector>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

#define NMAX 100001

struct nod {
	int U;
	nod *next;
};
nod *v[NMAX];
nod *T[NMAX];

int i, j, N, M;
int nrComp;
int A, B;

vector <int> Sorted;
vector <int> Comp[NMAX];

void add(int A, int B, nod *v[]) {
	nod *P = new nod;
	P->U = B;
	P->next = v[A];
	v[A] = P;
}

bool used[NMAX];

void TSort(int node) {
	used[node] = true;
	for (nod *it = v[node]; it; it = it->next) {
		if (!used[it->U])
			TSort(it->U);
	}
	Sorted.push_back(node);
}

void Kosaraju(int node) {
	used[node] = true;
	Comp[nrComp].push_back(node);
	for (nod *it = T[node]; it; it = it->next) {
		if (!used[it->U])
			Kosaraju(it->U);
	}
}

int main() {
	fin >> N >> M;
	for (i = 1; i <= M; ++i) {
		fin >> A >> B;
		add(A, B, v);
		add(B, A, T);
	}
	for (i = 1; i <= N; ++i) 
		if (!used[i])
			TSort(i);
	memset(used, 0, sizeof(used));
	vector <int> :: reverse_iterator it;
	for (it = Sorted.rbegin(); it != Sorted.rend(); ++it) {
		if (!used[*it]) {
			++nrComp;
			Kosaraju(*it);
		}
	}
	fout << nrComp << '\n';
	vector <int> :: iterator It;
	for (i = 1; i <= nrComp; ++i) {
		for (It = Comp[i].begin(); It != Comp[i].end(); ++It)
			fout << *It << ' ';
		fout << '\n';
	}
	return 0;
}