The third programming competition of Wuhan University of technology b- save the kingdom of DAG (topological properties deal with accessibility Statistics)

TP

The problem surface does not say that it must be a connected graph , For this reason, I also judged the data of the underworld

Such questions can be classified into DAG Accessibility statistics . When the data is small, such as $10^4$ Left and right can be used $bitset$ Pressure potential operation , Topological order dp Statistics ; But the data range of this question obviously does not allow this , So we need some fairy conclusions .

Take a look at the notes , It can only be said that God in God .

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#define debug cout << "debug--- "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 3e5 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

struct edge
{
    
    int a, b;
}ed[M];
vector<int> e[N];
int d[N], f[N];//f  Record the number of points that can be reached at any point （ But it should meet the definition of a first-class city ）

void top_sort() {
    
    int tot = n;// Number of remaining cities 
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (d[i] == 0) {
    
            tot--;// Join the team and subtract 
            q.push(i);
        }
    while (q.size())
    {
    
        int t = q.front();
        q.pop();

        // According to the properties of topological order , If the queue has multiple points on the same layer , These points are definitely not reachable , If you can , Then they must have different layers 

        // According to the meaning , If and only if there are two points within the same layer ：

        if (q.size() <= 1) {
    
            bool flag = true;
            if (q.size()) {
     
                for (int j : e[q.front()])
                    if (d[j] == 1)flag = false;
                // It is necessary to judge whether this extra point has a separate connection point , If you have,  t  Point can't go to him and his point , dissatisfaction  B  class 

                // If the degree is not  1, obviously  t  The point also has an edge connected to that point , No effect 
            }
            if (flag)f[t] += tot;
            // The remaining cities are made up of  t  Derived from topology , There must be a path 
        }

        for (int j : e[t])
            if (--d[j] == 0) {
    
                tot--;
                q.push(j);
            }
    }
}


void solve() {
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        d[b]++;
        ed[i] = {
     a,b };
    }

    top_sort();

    forr(i, 1, n)e[i].clear(), d[i] = 0;

    for (int i = 1; i <= m; i++) {
    
        int a = ed[i].a, b = ed[i].b;
        e[b].push_back(a);
        d[a]++;
    }

    // You have to run in reverse 
    top_sort();
    
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] >= n - 2)ans++;
    // Remove itself and a point that can be deleted 

    cout << ans;
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
    
        solve();
    }
    return 0;
}
/* */