Cod sursa(job #463349)

Utilizator plastikDan George Filimon plastik Data 15 iunie 2010 11:11:19
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.23 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 inStack[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 ++;
	Stack[numStack ++] = a;
	inStack[a] = 1;
	
	Node *curr;
	for (curr = Next[a]; curr != NULL; curr = curr->next) {
		if (Num[curr->b] == -1) {
			tarjan(curr->b);
			if (Low[a] > Low[curr->b])
				Low[a] = Low[curr->b];
		} else if (inStack[curr->b] && Low[a] > Num[curr->b])
			Low[a] = Num[curr->b];
	}
	int i;
	if (Low[a] == Num[a]) {
		i = 0;
		//fprintf(stderr, "%d:\n", numSCC);
		while (numStack > 0 && Low[Stack[numStack - 1]] >= Num[a]) {
			addSCC(numSCC, Stack[numStack - 1]);
			//fprintf(stderr, "%d ", Stack[numStack - 1] + 1);
			inStack[Stack[numStack - 1]] = 0;
			-- numStack;
		}
		++ numSCC;
		//fprintf(stderr, "\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) {
		Num[i] = -1;
		inStack[i] = 0;
	}
	for (i = 0; i < n; ++ i)
		if (Num[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;
}