1 / 2
Jan 2014

I was trying the problem http://www.spoj.com/problems/BOTTOM/2 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;
}
  • created

    Jan '14
  • last reply

    Jan '15
  • 1

    reply

  • 277

    views

  • 2

    users

  • 1

    link

12 months later

Hey the WA is because you are printing a[i]+ " " then if there is only one answer you print "2 " and the answer is "2"

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 17 11d

Want to read more? Browse other topics in C and C++ or view latest topics.