201509-4 ccf 高速公路（强连通分量 tarjan算法）

不念不忘少年蓝@ 2022-05-14 02:58 184阅读 0赞

题目链接：  
[高速公路][Link 1]

题目大意：  
中文题，不解释

解题思路：  
抽象出来，其实就是求强连通分量，求出每个强连通分量的点的个数后，点对的个数就是C(强连通分量点的个数，2）（C是组合数学的组合符号）。板子题，多希望每年都是板子题2333，祈祷18年

AC代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    const int MAXN = 1e5;
    
    int dfn[MAXN],low[MAXN],vis[MAXN],stack[MAXN],num[MAXN];
    int n,m,ans,time,top,cnt;
    
    vector<int> g[MAXN];
    
    int C(int a, int b){
        int fz = 1,fm = 1;
        for(int i=b; i>0; i--){
            fz *= (a-i+1);
            fm *= i;
        }
        return fz/fm;
    }
    
    void tarjan(int u){
        dfn[u] = low[u] = ++time;
        vis[u] = 1;
        stack[++top] = u;
        for(int j=0; j<g[u].size(); ++j){
            int v = g[u][j];
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }else if(vis[v]){
                low[u] = min(low[u], dfn[v]);
            }
        }
    
        if(dfn[u] == low[u]){
            int t;
            cnt++;
            do{
                t = stack[top];
                vis[t] = 0;
                num[cnt]++;
                top--;
            }while(t!=u);
        }
    }
    
    void init(){
        memset(dfn, 0, sizeof(dfn));
        memset(vis, 0, sizeof(vis));
        memset(stack, 0, sizeof(stack));
        memset(num, 0, sizeof(num));
        ans = time = top = cnt = 0;
    }
    
    int main(){
        init();
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
        }
    
        for(int i=1; i<=n; ++i){
            if(!dfn[i]) tarjan(i);
        }
    
        for(int i=1; i<=cnt; ++i){
            if(num[i]>1) ans += C(num[i],2);
        }
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T29