Pagini recente » Cod sursa (job #1137907) | Cod sursa (job #3253998) | Cod sursa (job #2492629) | Cod sursa (job #2878976) | Cod sursa (job #463300)
Cod sursa(job #463300)
// 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;
}