WA 70

刚学 topo 的萌新求助 QAQ

具体思路：虚点连边 + topo + 统计答案，分别体现在 begin()、topo()、end() 中。

错的三个点的输出均比答案大一。

# define _CRT_SECURE_NO_WARNINGS
# include <cstdio>
# include <queue>

typedef short unsigned int hu;
enum { N = 1000, M = 1000 };

struct Vertex {
    std::vector<hu> out;
    hu in_degree;
    hu ans;
};

static hu n, m;
static Vertex v[N + M + 1];
static hu ans;

inline const void add(const hu a, const hu b) { v[a].out.push_back(b), ++v[b].in_degree; }
inline const void begin() {
    scanf("%hu%hu", &n, &m);
    static bool t[N + 1];
    for (register hu i(0); i < m; ++i) {
        for (register hu j(1); j <= n; ++j) t[j] = false;
        static hu s; scanf("%hu", &s);
        static hu f, l;
        scanf("%hu", &f), t[f] = true;
        for (register hu j(1); j < s; ++j) scanf("%hu", &l), t[l] = true;
        for (register hu j(f); j <= l; ++j)
            if (t[j]) add(n + i + 1, j);
            else add(j, n + i + 1);
    }
}
inline const void end() {
    bool w[N + M]{};
    for (register hu i(1); i <= n; ++i) w[v[i].ans] = true;
    for (register hu i(0); i < n + m; ++i) ans += w[i];
    printf("%hu\n", ans);
}

inline const void topo() {
    std::queue<hu> q;
    for (register hu i(1); i <= n + m; ++i) if (not v[i].in_degree) v[i].ans = 0, q.push(i);
    while (not q.empty()) {
        const hu t(q.front()); q.pop();
        for (register hu i(0); i < v[t].out.size(); ++i)
            if (not--v[v[t].out[i]].in_degree)
                v[v[t].out[i]].ans = v[t].ans + 1, q.push(v[t].out[i]);
    }
}

signed int main() {
    begin();
    topo();
    end();
    return 0;
}