学渣乱搞系列之Tarjan模板合集

学渣乱搞系列之Tarjan模板合集

　　　　　　　　　　　　by　狂徒归来

一、求强连通子图

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 int dfn[maxn],low[maxn],belong[maxn];

 bool instack[maxn];

 vector<int>g[maxn];

 stack<int>stk;

 int n,m,cnt,scc;

 void tarjan(int u) {

     dfn[u] = low[u] = ++cnt;

     stk.push(u);

     instack[u] = true;

     for(int i = ; i < g[u].size(); i++) {

         if(!dfn[g[u][i]]) {

             tarjan(g[u][i]);

             low[u] = min(low[u],low[g[u][i]]);

         } else if(instack[g[u][i]]) low[u] = min(low[u],dfn[g[u][i]]);

     }

     if(dfn[u] == low[u]) {

         scc++;

         int v;

         do {

             v = stk.top();

             instack[v] = false;

             belong[v] = scc;

             stk.pop();

         } while(v != u);//每一个强连通块内de点，以及其属于的scc

     }

 }

 int main() {

     int i,j,u,v,a,b;

     while(~scanf("%d %d",&n,&m)) {

         for(i = ; i <= n; i++) {

             dfn[i] = belong[i] = ;

             instack[i] = false;

             g[i].clear();

         }

         cnt = scc = ;

         while(!stk.empty()) stk.pop();

         for(i = ; i <= m; i++) {

             scanf("%d %d",&u,&v);

             g[u].push_back(v);

         }

         for(i = ; i <= n; i++)

             if(!dfn[i]) tarjan(i);

     }

     return ;

 }

二、求割点

 const int maxn = ;

 vector<int>g[maxn];

 bool iscut[maxn];

 int dfn[maxn],low[maxn],cnt,vis[maxn];

 void tarjan(int u,int fa) {

     dfn[u] = low[u] = ++cnt;

     vis[u] = ;

     int son = ;

     for(int i = ; i < g[u].size(); i++) {

         if(!vis[g[u][i]]) {

             tarjan(g[u][i],u);

             son++;

             low[u] = min(low[u],low[g[u][i]]);

             if(fa == - && son >  || fa != - && low[g[u][i]] >= dfn[u])

                 iscut[u] = true;

         } else if(vis[g[u][i]] == ) low[u] = min(low[u],dfn[g[u][i]]);

     }

     vis[u] = ;

 }

三、求割边/桥

 int ret;

 void tarjan(int u,int fa) {

     dfn[u] = low[u] = ++clk;

     bool flag = false;

     for(int i = head[u]; ~i; i = e[i].next) {

         if(!flag && e[i].to == fa) {

             flag = true;

             continue;

         }

         if(!dfn[e[i].to]) {

             tarjan(e[i].to,u);

             low[u] = min(low[u],low[e[i].to]);

             if(low[e[i].to] > dfn[u]) {

                 e[i].cut = e[i^].cut = true;

                 ++ret;

             }

         } else low[u] = min(low[u],dfn[e[i].to]);

     }

 }

四、求LCA