首页 > 代码库 > ZOJ 3795 Grouping 强连通分量-tarjan

ZOJ 3795 Grouping 强连通分量-tarjan

2024-07-16 18:58:22   220人阅读

一开始我还天真的一遍DFS求出最长链以为就可以了

不过发现存在有向环，即强连通分量SCC，有向环里的每个点都是可比的，都要分别给个集合才行，最后应该把这些强连通分量缩成一个点，最后保证图里是 有向无环图才行，这个时候再找最长链，当然缩点之后的scc是有权值的，不能只看成1，缩点完了之后，用记忆化搜索DP就可以再On的复杂度内求出结果

所以现学了一下SCC-Tarjan，所谓Scc-tarjan，就是找到强连通分量并且缩点，特别好用，其原理就是利用dfs时间戳，每个点有自己的时间戳，同时再开一个记录通过孩子的路径能指向的最上边的节点的时间戳，lowlink，如果当前lowlink就等于自己，即找到了强连通分量，并且找到了最大的头头。所以一个点也是强连通分量

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <stack>using namespace std;const int N = 100010;stack<int> sta;vector <int> G[N];vector <int> G4[N];int vis[N];int n,m;int pre[N],lowlink[N],sccno[N],w[N],dfs_clk,scc_cnt;int dp[N];void init(){    dfs_clk=scc_cnt=0;    for (int i=0;i<=n;i++){        G[i].clear();        pre[i]=0;        lowlink[i]=0;        sccno[i]=0;        vis[i]=0;        w[i]=0;        G4[i].clear();    }}void dfs(int u){    pre[u]=lowlink[u]=++dfs_clk;    sta.push(u);    for (int i=0;i<G[u].size();i++){        int v=G[u][i];        if (!pre[v]){            dfs(v);            lowlink[u]=min(lowlink[u],lowlink[v]);        }        else if (!sccno[v]){            lowlink[u]=min(lowlink[u],pre[v]);        }    }    if (lowlink[u]==pre[u]){        scc_cnt++;        for (;;){            int x=sta.top();sta.pop();            sccno[x]=scc_cnt;            w[scc_cnt]++;            if (x==u) break;        }    }}void tarjan(){    for (int i=1;i<=n;i++){        if (!pre[i]) dfs(i);    }}void calc(int u){    if (dp[u]!=-1) return;    dp[u]=w[u];    int now=w[u];    for (int j=0;j<G4[u].size();j++){        int v=G4[u][j];        calc(v);        dp[u]=max(dp[u],dp[v]+now);    }}void solve(){    for (int i=1;i<=n;i++){        int u=sccno[i];        for (int j=0;j<G[i].size();j++){            int v=sccno[G[i][j]];            if (u!=v) G4[u].push_back(v);        }    }    for (int i=1;i<=scc_cnt;i++){        dp[i]=-1;    }    for (int i=1;i<=scc_cnt;i++){        calc(i);    }    int ans=0;    for (int i=1;i<=scc_cnt;i++){        ans=max(ans,dp[i]);    }    printf("%d\n",ans);}int main(){    while (scanf("%d%d",&n,&m)!=EOF)    {        init();        int a,b;        while (m--)        {            scanf("%d%d",&a,&b);            G[a].push_back(b);        }        tarjan();        solve();    }    return 0;}

 


联系
我们