武汉理工大学第三届程序设计竞赛 B-拯救DAG王国（拓扑性质处理可达性统计问题）

TP

题面没说一定是连通图，为此还去特判了下阴间数据

此类题可归类到 DAG的可达性统计。当数据小的时候比如 $10^4$ 左右可以用 $bitset$ 压位运算，拓扑序 dp 统计；但此题的数据范围显然不允许这样做，所以就需要一些神仙结论了。

看注释吧，只能说神中神。

$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 记录任意点可到达的点数（但要符合一流城市定义）

void top_sort() {
    
    int tot = n;//剩余城市数量
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (d[i] == 0) {
    
            tot--;//入队就减去
            q.push(i);
        }
    while (q.size())
    {
    
        int t = q.front();
        q.pop();

        //根据拓扑序的性质，如果队列同层有多个点，这些点之间肯定不能抵达，如果能，则他们肯定不同层

        //根据题意，当且仅当同层有两个点以内时：

        if (q.size() <= 1) {
    
            bool flag = true;
            if (q.size()) {
     
                for (int j : e[q.front()])
                    if (d[j] == 1)flag = false;
                //需要特判这个额外点是否有单独的连接点，如果有则 t 点走不到他和他的点，不满足 B 类

                //如果度数不为 1，显然 t 点也有连向那个点的边，不影响
            }
            if (flag)f[t] += tot;
            //剩余城市都是由 t 拓扑推导出来的，肯定存在路径
        }

        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]++;
    }

    //反向也要跑一遍
    top_sort();
    
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] >= n - 2)ans++;
    //除去自身和一个可以删去的点

    cout << ans;
}

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