CCF 高速公路

红太狼 2021-09-14 03:12 291阅读 0赞

## **一、试题** ##

问题描述  
　　某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。  
　　现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。  
　　国王想知道，在大臣们给他的计划中，有多少个便利城市对。  
输入格式  
　　输入的第一行包含两个整数n, m，分别表示城市和单向高速公路的数量。  
　　接下来m行，每行两个整数a, b，表示城市a有一条单向的高速公路连向城市b。  
输出格式  
　　输出一行，包含一个整数，表示便利城市对的数量。  
样例输入  
5 5  
1 2  
2 3  
3 4  
4 2  
3 5  
样例输出  
3  
样例说明

城市间的连接如图所示。有3个便利城市对，它们分别是(2, 3), (2, 4), (3, 4)，请注意(2, 3)和(3, 2)看成同一个便利城市对。  
评测用例规模与约定  
　　前30%的评测用例满足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000；  
　　前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000；  
　　所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。

## **二、代码** ##

[Tarjan算法][Tarjan]

#include <cstdio>
    #include <stack>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    #define NNMAX 10010
    
    int n,m,time;
    int DFN[NNMAX];
    int LOW[NNMAX];
    
    stack<int> s;  //DFS栈
    vector<int> G[NNMAX];
    
    int visit[NNMAX];    //记录是否访问，因为整个节点我们只访问一次就行。
    int instack[NNMAX]; //判断是否在栈里
    int total;
    
    void tarjan(int u){
    
        DFN[u]=LOW[u]=++time; //次序从1开始，初始时由于默认将DFN[u]=LOW[u]都置为次序号
        // 将当前节点压栈，置位在栈中，已访问。
        visit[u]=1;
        s.push(u);
        instack[u]=1;
    
    
        //取u节点的下一路径节点v,当没有v可取时也说明深度搜索已经到达当前最底部，这是我们函数返回寻找另一条路径。
        for(int j=0;j<G[u].size();j++){
            int v=G[u][j];
            if(visit[v]==0){
                tarjan(v);
                // 在深度搜索返回时，如果v节点下存在子树，要将u节点的LOW[u]更新。
                LOW[u]=min(LOW[u],LOW[v]);
    
            }else if(instack[v]){
                // v节点已经被访问，并且在栈中，说明在当前路径上存在环，此处只是赋值，但并不代表在u子树的底下的多个节点没有比当前环更大的环。无法作为深度终止条件。
                LOW[u]=min(LOW[u],DFN[v]);
            }
        }
    
        int m;
        int num=0; //对一个环计数计数
        // 在深度搜索完结后返回时，判断DFN[u]==LOW[u]，相等说明找到了一个环，将栈中节点弹出。注意tarjan算法认为单个节点也为环。
        if(DFN[u]==LOW[u]){
            // 将栈中节点弹出，并计数
            do{
                m=s.top();
                s.pop();
                instack[m]=0;
                num++;
            }while(m!=u);
    
            // 只有环内节点数大于两个才是真正环。
            if(num>1){
                // n个点两两相交（互相到达），则有n*(n-1)/2条连接线
                total+=num*(num-1)/2;
            }
        }
    
    }
    int main(){
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++){
            int s,e;
            scanf("%d %d",&s,&e);
            // 使用邻接表存储路径信息，方便调用
            G[s].push_back(e);
        }
    
        // 由于可能存在多个完全不连通的图，因此需要把所有节点都要访问到
        for(int i=1;i<=n;i++){
            if(visit[i]==0){
                visit[i]=1;
                tarjan(i);
            }
        }
        printf("%d",total);
    
        return 0;
    }

[Tarjan]: http://blog.csdn.net/qq_16234613/article/details/77431043