CSP 高速公路强连通分量 tarjan-白红宇

CSP 高速公路强连通分量 tarjan

阅读量：4216 次

发布时间：2019-05-26

本文共 1168 字，大约阅读时间需要 3 分钟。

题目：

思路：

#include
   
    #include
    
     #include
     
      #include
      
       #define MAXN 10000+5#define MAXM 100000+5#include
       
        using namespace std; bool in_stack[MAXN];bool vis[MAXN];int low[MAXN];int dfn[MAXN];stack
        
          s;int cur_time,color;int col_num[MAXN];int n,m;vector
         
           adj[MAXN];int tarjan(int cur) { dfn[cur] = low[cur] = ++cur_time; s.push(cur); in_stack[cur] = true; vis[cur] = true; for(int i = 0; i < adj[cur].size(); ++i){ int v = adj[cur][i]; if(!vis[v]){ tarjan(v); low[cur] = min(low[v],low[cur]); } else if(in_stack[v]){ low[cur] = min(low[cur],dfn[v]); } } if(dfn[cur] == low[cur]){ ++color; int v; do{ v = s.top(); s.pop(); in_stack[v] = false; ++col_num[color]; }while(v != cur); } }int main() { scanf("%d%d",&n,&m); memset(vis,false,sizeof(vis)); memset(in_stack,false,sizeof(in_stack)); for(int i = 0; i < m; ++i){ int f,t; scanf("%d%d",&f,&t); adj[f].push_back(t); } cur_time = 0; color = 0; for(int i = 1; i <= n; ++i){ if(!vis[i]){ tarjan(i); } } int ans = 0; for(int i = 1; i <= color; ++i){ if(col_num[i] > 1){ int x = col_num[i]; ans += (x*(x-1)/2); } } printf("%d\n",ans); return 0; }