Submission #73513056

---

Source Code Expand

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        g[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
    vector<int> p(n + 1, 0);
    
    int num = 1;
    vector<bool> f(n + 1, false); 
    set<int> h;
    h.insert(1), f[1] = true;
    
    set<int> ans;
    for (int x : g[1]) if (x != 1) ans.insert(x);
    for (int i = 1; i <= n; i++) {
        set<int> a, d;
        for (int x : h) {
            int sz = g[x].size();
            while (p[x] < sz && g[x][p[x]] <= i) {
                int y = g[x][p[x]++];
                if (!f[y]) f[y] = true, num++, a.insert(y);
            }
            if (p[x] == sz) d.insert(x);
        }
        if (f[i]) {
            if (ans.count(i)) ans.erase(i);
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int x = q.front(); q.pop();
                int sz = g[x].size();
                while (p[x] < sz && g[x][p[x]] <= i) {
                    int y = g[x][p[x]++];
                    if (!f[y]) f[y] = true, num++, a.insert(y), q.push(y);
                }
                if (p[x] == sz) d.insert(x);
            }
        }
        for (int x : a) {
            h.insert(x);
            for (int j = p[x]; j < (int) g[x].size(); j++) ans.insert(g[x][j]);
        }
        for (int x : d) h.erase(x);
        
//        cout << "i= " << i << ", num= " << num << '\n';
        if (num == i) {
            cout << ans.size() << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
    
    return 0;
}

Submission Info

Judge Result