Cow Contest

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5000;

int n, m;
int p[N];
int in[N];
int q[N];
bool st[N][N];

int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    int fa = find(a), fb = find(b);
    p[fa] = fb;
}

int topsort() {
    int res = 0;
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )

        if (!in[i])
            q[ ++ tt ] = i;

    while (hh <= tt) {
        int t = q[hh ++ ];

        if (hh == tt + 1) {
            int i;

            for (i = 0; i <= tt; i ++ )

                if (!st[q[i]][t])
                    break;

            if (i == tt + 1)
                res ++ ;
        }

        for (int j = 1; j <= n; j ++ ) {

            if (st[t][j]) {
                in[j] -- ;

                for (int i = 0; i <= tt; i ++ )

                    st[q[i]][j] |= st[q[i]][t];

                if (in[j] == 0)
                    q[ ++ tt ] = j;
            }
        }
    }

    return res;
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) {

        p[i] = i;
        st[i][i] = true;
    }

    while (m -- ) {
        int a, b;
        scanf("%d%d", &a, &b);
        st[a][b] = true;
        in[b] ++ ;
        merge(a, b);
    }

    int cnt = 0;

    for (int i = 1; i <= n; i ++ )

        if (p[i] == i)
            cnt ++ ;

    if (cnt > 1)
        puts("0");
    else
        printf("%d\n", topsort());
    return 0;
}

确定比赛名次

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

const int N = 510;

int h[N], e[N], ne[N], idx;
int n, m;
int in[N];
int ans[N], cnt;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    priority_queue<int, vector<int>, greater<int>> teap;

    for (int i = 1; i <= n; i ++ )

        if (!in[i])
            teap.push(i);

    while (teap.size()) {
        int t = teap.top();
        teap.pop();
        ans[cnt ++ ] = t;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (-- in[j] == 0)
                teap.push(j);
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(h, -1, sizeof h);
        idx = 0;
        memset(in, 0, sizeof in);
        cnt = 0;

        while (m -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            in[b] ++ ;
            add(a, b);
        }

        topsort();

        for (int i = 0; i < n; i ++ ) {

            if (i != n - 1)
                printf("%d ", ans[i]);
            else
                printf("%d\n", ans[i]);
        }
    }

    return 0;
}

Task schedule

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

const int N = 50010;

int h[10 * N], e[10 * N], ne[10 * N], idx;
int n, m;
int in[N];
int ans[N], cnt;

struct node {
    int ver;
    int d;
    bool operator<(const node &t)const {
        return t.d < d;
    }
} job[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    priority_queue<int, vector<int>, greater<int>> teap;

    for (int i = 1; i <= n; i ++ )

        if (!in[i])
            teap.push(i);

    while (teap.size()) {
        int t = teap.top();
        teap.pop();
        ans[cnt ++ ] = t;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (-- in[j] == 0)
                teap.push(j);
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    idx = 0;

    for (int i = 1; i <= n; i ++ ) {

        int p;
        scanf("%d%d", &p, &job[i].d);
        job[i].ver = i;
    }

    scanf("%d", &m);

    while (m -- ) {

        int a, b;
        scanf("%d%d", &a, &b);
        in[b] ++ ;
        add(a, b);
    }

    topsort();

    for (int i = 0; i < n; i ++ )

        printf("%d\n", ans[i]);
    return 0;
}