tarjan算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了tarjan算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1229字，纯文字阅读大概需要2分钟。

内容图文

• 每次向下搜点,\(dfn[i]\)表示搜到第\(i\)点时的编号,\(low[i]\)表示第\(i\)个点能到达的最小的点的编号,我们在搜的时候可以把路径上的点存入到栈中,当\(dfn[i]=low[i]\)时,说明我们已经找完一个强连通子图了,此时就可以把栈中的元素出栈得到一个强连通子图.

• 代码:

  #include <bits/stdc++.h>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
   
   int n,m;
   vector<int> edge[N];
   int dfn[N],low[N],timestamp;
   int stk[N],top;
   bool in_stk[N];
   int id[N],scc_cnt;
  
  void tarjan(int u){
      dfn[u]=low[u]=++timestamp;
      stk[++top]=u,in_stk[u]=true;
      for(auto w:edge[u]){
          if(!dfn[w]){
              tarjan(w);
              low[u]=min(low[u],low[w]);
          }
          else if(in_stk[w]) low[u]=min(low[u],dfn[w]);
      }
  
      if(dfn[u]==low[u]){
          ++scc_cnt;
          int y;
          do{
              y=stk[top--];
              in_stk[y]=false;
              id[y]=scc_cnt;
          }while(y!=u);
      }
  }
   
  int main(){
      ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
      cin>>n>>m;
  
      rep(i,1,m){
          int u,v;
          cin>>u>>v;
          edge[u].pb(v);
      }
  
      rep(i,1,n){
          if(!dfn[i]) tarjan(i);
      }
   
      return 0;
  }
  

内容总结

以上是互联网集市为您收集整理的tarjan算法全部内容，希望文章能够帮你解决tarjan算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---