题目描述

数一个拓扑图边的条数，要求边包含至少两个点，且无法更长（起点入度为0，终点出度为0）

思路

topo排序+简单dp，建个反图方便dp

样例

in:
10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

out:
9

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 4 * N;
int n, m, q[N], din[N];
int idx, h[N], e[M], ne[M], hs[N], dp[N], dout[N];
bool st[N];
void add(int h[], int a, int b){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

bool topoSort(){
    int tt = -1, hh = 0;
    for(int i = 1; i <= n; i ++ )
    if(!din[i]) q[ ++ tt] = i, st[i] = true;
    while(hh <= tt){
        int t = q[hh ++ ];
        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(--din[j] == 0) q[ ++ tt] = j;
        }
    }
    return tt == n - 1;

}

int main(){
    while(cin >> n >> m){
        idx = 0;
        memset(st, 0, sizeof st);
        int res = 0;
        memset(h, -1, sizeof h);
        memset(hs, -1, sizeof hs);
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        memset(dp, 0, sizeof dp);
        while(m -- ){
            int a, b;
            cin >> a >> b;
            add(h, a, b);
            add(hs, b, a);
            din[b] ++;
            dout[a] ++;
        }

        if(topoSort()){
    //        for(int i = 0; i < n; i ++ ) cout << q[i] << " ";
            for(int i = 0; i < n; i ++ ){
                int j = q[i];
                for(int k = hs[j]; ~k; k = ne[k]){
                    int t = e[k];
                    dp[j] += dp[t];
                    if(st[t]) dp[j] ++; // 这样保证边大于1
                }
            }
            for(int i = 1; i <= n; i ++ )
                if(dout[i] == 0) res += dp[i];
            cout << res << endl;
        }
    }
    return 0;
}