Cod sursa(job #1536579)

Utilizator kassay_akosKassay Akos kassay_akos Data 26 noiembrie 2015 13:30:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stack>

using namespace std;
const int nmax = 100003;

vector <int> G[nmax], invG[nmax];
int k,n,len;
int visited[nmax],result[nmax];
stack <int> S;


void Melysegi(int ind);
void MelysegiInv(int ind);

int main(){
	int m, a, b;
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	scanf("%d %d", &n, &m);

	for (; m--;) {
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		invG[b].push_back(a);
	}

	memset(visited, 0, 4 * (n + 2));

	// KUsaraju
	for (int i = 1; i <= n; i++) {
		if (visited[i] == 0) Melysegi(i);
	}

	memset(visited, 0, 4 * (n + 2));
	memset(result, -1, 4 * (n + 2));
	k = 0; len = 0;
	while (!S.empty()) {
		if (visited[S.top()] == 0) {
			k++;
			MelysegiInv(S.top());
		}
		S.pop();
	}

	// done

	printf("%d", k);
	k = 0;
	for (int i = 0; i < len; i++) {
		if (visited[result[i]] == k) printf(" %d", result[i]);
		else						{ printf("\n%d", result[i]); k++; }
	}

	fclose(stdout);
	fclose(stdin);
	return 0;
}

void Melysegi(int ind) {
	visited[ind] = 1;
	for (int j = 0; j < G[ind].size(); j++) {
		if (visited[G[ind][j]] == 0) Melysegi(G[ind][j]);
	}
	S.push(ind);
}


void MelysegiInv(int ind) {
	visited[ind] = k;
	result[len++] = ind;
	for (int j = 0; j < invG[ind].size(); j++) {
		if (visited[invG[ind][j]] == 0) MelysegiInv(invG[ind][j]);
	}
}