原题：Proving Equivalences

原题大意

给出N个命题，要求你证明这N个命题的等价性：比如有4个命题a,b,c,d，我们证明a<->b, b<->c,c<->d，每次证明都是双向的，因此一共用了6次推导如果换成证明a->b,b->c,c->d,d->a,每次证明都是单向的，而只需4次就可以证明所有命题的等价性现在给出M个命题证明，问还需要证明几个，才可以保证N个命题等价。

算法分析

缩点后求DAG中入度为0和出度为0的联通块的较大值

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e4+5;
vector<int> G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> S;
int T, n, m;
int ind[maxn], outd[maxn];
void dfs(int u){
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v]){
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if(lowlink[u] == pre[u]){
        scc_cnt++;
        for(;;){
            int x = S.top();S.pop();
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}
void find_scc(int n){
    dfs_clock = scc_cnt = 0;
    mem(sccno, 0);
    mem(pre, 0);
    for(int i = 1; i <= n; i++)
        if(!pre[i]) dfs(i);
}
void Init(){
    for(int i = 0; i <= n; i++)G[i].clear();
    mem(ind, 0);
    mem(outd, 0);
}
int main(){
  //  freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> m;
        Init();
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            G[u].pb(v);
        }
        find_scc(n);
        for(int u = 1; u <= n; u++)
            for(int i = 0; i < G[u].size(); i++){
                int v = G[u][i];
                if(sccno[v] != sccno[u]){
                    outd[sccno[u]]++;
                    ind[sccno[v]]++;
                }
            }
        int a = 0, b = 0;
        for(int i = 1; i <= scc_cnt; i++){
            if(!ind[i]) a++;
            if(!outd[i]) b++;
        }
        int ans = max(a, b);
        if(scc_cnt == 1) ans = 0;
        cout << ans << "\n";
    }
    return 0;
}