ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
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);
a[j].push_back(i);
++ 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;
}
}

printf("YES\n");
return 0;
}