I was trying the problem http://www.spoj.com/problems/BOTTOM/ but I am getting wrong answer. I have used kosaraju's algorithm of strongly connected components.After finding out all SCCs I have removed those SCC in which there is a edge directing to any other SCC. I have also kept in mind that graph can be discontinuous. please help asap.
here is my code..
#include <stdio.h>
#include <stdlib.h>
int t = 0;
int lead = 0;
int mark = 0;
int arr[5001];
struct head
{
int val;
int color;
struct node *l;
};
struct node
{
int val;
struct node *prev;
struct node *next;
};
void dfs(struct head a[], int s)
{
a[s].color = 1;
while (a[s].l != NULL) {
if (a[a[s].l->val].color == 0) {
dfs(a, a[s].l->val);
}
a[s].l = a[s].l->next;
}
t++;
arr[t] = a[s].val;
}
void dfs1(struct head a[], int s)
{
a[s].color = 1;
a[s].val = lead;
while (a[s].l != NULL) {
if (a[a[s].l->val].color == 2) {
mark = -1;
}
if (a[a[s].l->val].color == 0) {
dfs1(a, a[s].l->val);
}
a[s].l = a[s].l->next;
}
a[s].color = 2;
}
int main()
{
while (1) {
int n, m;//n = vertices m = edges.
int x, y;
int i;
scanf("%d", &n);
if (n == 0) {
break;
}
scanf("%d", &m);
struct head a[n + 1];//graph;
struct head arev[n + 1];//keep graph_rev;
int ans[n + 1];//mark those vertices 1 which are leaders and sink;
t = 0;
lead = 0;
for (i = 1; i <= n; i++) {
ans[i] = 0;
}
for (i = 1; i <= n; i++) {
a[i].color = 0;
a[i].val = i;
a[i].l = NULL;
arev[i].color = 0;
arev[i].l = NULL;
arev[i].val = i;
}
struct node *k, *t;
for (i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
k = a[x].l;
if (k == NULL) {
k = (struct node *)malloc(sizeof(struct node));
k->val = y;
k->prev = NULL;
k->next = NULL;
a[x].l = k;
} else {
t = k;
k = k->next;
while(k != NULL) {
k = k->next;
t = t->next;
}
struct node *q;
q = (struct node *)malloc(sizeof(struct node));
q->val = y;
q->next = NULL;
q->prev = t;
t->next = q;
}
k = arev[y].l;
if (k == NULL) {
k = (struct node *)malloc(sizeof(struct node));
k->val = x;
k->prev = NULL;
k->next = NULL;
arev[y].l = k;
continue;
}
t = k;
k = k->next;
while(k != NULL) {
k = k->next;
t = t->next;
}
struct node *q;
q = (struct node *)malloc(sizeof(struct node));
q->val = x;
q->next = NULL;
q->prev = t;
t->next = q;
}
for (i = n; i >= 1; i--) {
if (arev[i].color == 0) {
dfs(arev, i);
}
}
for (i = n; i >= 1; i--) {
if (a[arr[i]].color == 0) {
lead = arr[i];
mark = 0;
dfs1(a, lead);
if (mark == 0) {
ans[lead] = 1;
}
}
}
for (i = 1; i <= n; i++) {
if (ans[a[i].val] == 1) {
printf("%d ", i);
}
}
printf("\n");
}
return 0;
}