Cod sursa(job #463300)

Utilizator plastikDan George Filimon plastik Data 14 iunie 2010 22:31:50
Problema Componente tare conexe Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 2.19 kb
// http://infoarena.ro/problema/ctc

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int b;
	struct node *next;
} Node;

Node **Next;
int n, m;

#define NMAX 100005
char Used[NMAX];
int Stack[NMAX], Num[NMAX], Low[NMAX], Pred[NMAX];

void addNext(int a, int b) {
	Node *helper = (Node*)calloc(1, sizeof(Node));
	helper->b = b;
	helper->next = Next[a];

	Next[a] = helper;
}

void eraseNext() {
	int i;
	Node *curr, *helper;
	for (i = 0; i < n; ++ i) 
		for (curr = Next[i]; curr != NULL; curr = helper) {
			helper = curr->next;
			free(curr);
		}	
	free(Next);
}

int num = 1, numStack = 0, numSCC = 0;
Node **SCC;

inline void addSCC(int i, int val) {
	Node *helper = (Node*)calloc(1, sizeof(Node));
	helper->b = val;
	helper->next = SCC[i];
	SCC[i] = helper;
}

void eraseSCC() {
	int i;
	Node *curr, *helper;
	for (i = 0; i < numSCC; ++ i)
		for (curr = SCC[i]; curr != NULL; curr = helper) {
			helper = curr->next;
			free(curr);
		}
}

void tarjan(int a) {
	Num[a] = Low[a] = num ++;
	Node *curr;
	for (curr = Next[a]; curr != NULL; curr = curr->next) {
		if (!Used[curr->b]) {
			Pred[curr->b] = a;
			Used[curr->b] = 1;
			tarjan(curr->b);
			if (Low[a] > Low[curr->b])
				Low[a] = Low[curr->b];
		} else if (Low[a] > Num[curr->b])
			Low[a] = Num[curr->b];
	}
	Stack[numStack ++] = a;
	int i;
	if (Low[a] == Num[a]) {
		i = 0;
		// printf("%d:\n", ++ numSCC);
		while (numStack > 0 && Low[Stack[numStack - 1]] >= Num[a]) {
			// SCC[numSCC][i ++] = Stack[numStack - 1];
			addSCC(numSCC, Stack[numStack - 1]);
			// printf("%d ", Stack[numStack - 1] + 1);
			-- numStack;
		}
		++ numSCC;
		// printf("\n");
	}
}

int main() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	scanf("%d%d", &n, &m);
	Next = (Node**)calloc(n, sizeof(Node*));

	int i, a, b;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d", &a, &b);
		addNext(a - 1, b - 1);
	}
	
	SCC = (Node**)calloc(n, sizeof(Node*));
	for (i = 0; i < n; ++ i)
		if (!Used[i]) {
			Pred[i] = -1;
			Used[i] = 1;
			tarjan(i);
		}

	
	Node *curr;
	printf("%d\n", numSCC);
	for (i = 0; i < numSCC; ++ i) {
		for (curr = SCC[i]; curr != NULL; curr = curr->next)
			printf("%d ", curr->b + 1);
		printf("\n");
	}

	eraseSCC();
	eraseNext();
	return 0;
}