ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1280. Topological Sorting

What am I missing here??
Posted by Chen Tsung 25 Sep 2005 21:17
"Michael’s coach analyzed all subjects and prepared a list of M limitations in the form «si, ui» (1<= si, ui<= N; i=1, 2, ..., M), which means that subject si must be studied before subject ui"

I take every node in the given order, and check whether it satisfies the limitations (there is no subject that must be studied before or I have already studied a necessary subject). Otherwise I output "NO"...

But I get WA on test 16 :((((

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 1005

vector<int> a[MAXN];
int r[MAXN], seen[MAXN], deg[MAXN];
int N, M, i, j, qb, qe;

int main(void)
//    freopen("1280.in", "r", stdin);
    memset(deg, 0, sizeof(deg));
    for(scanf("%d %d", &N, &M); M; M --)
        scanf("%d %d", &i, &j);
        ++ deg[j];
    for (i = 0; i < N; i ++)
        scanf("%d", &(r[i]));

    memset(seen, 0, sizeof(seen));
    vector<int>::iterator it;

    for (i = 0; i < N; i ++)
        if (deg[r[i]] == 0)
            seen[r[i]] = 1; continue;

        bool fnd = false;
        for (it = a[r[i]].begin(); it != a[r[i]].end(); it ++)
            if (seen[*it])
                seen[r[i]] = 1; fnd = true; break;

        if (!fnd)
            printf("NO\n"); return 0;

    return 0;