洛谷 P1983. 车站分级

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N], din[N], has[N][N];
int n, m;
vector<int> g[N];

void topo() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!din[i]) {
            q.push(i);
            f[i] = 1;
        }
    }

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];

            f[v] = max(f[v], f[u] + 1);

            din[v]--;
            if (!din[v]) {
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int q;
        cin >> q;

        vector<int> vec;
        unordered_map<int, bool> st;
        for (int j = 1; j <= q; j++) {
            int x;
            cin >> x;
            vec.push_back(x);
            st[x] = true;
        }

        for (int i = vec[0]; i <= vec[q - 1]; i++) {
            if (!st[i]) {
                for (int j = 0; j < q; j++) {
                    if (!has[i][vec[j]]) {
                        din[vec[j]]++;
                        g[i].push_back(vec[j]);
                        has[i][vec[j]] = 1;
                    }
                }
            }
        }
    }

    topo();

    int mx = -1e9;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, f[i]);
    }
    cout << mx << endl;

    return 0;
}