首页 > 其他分享 >tarjan

tarjan

时间:2024-04-16 09:45:48浏览次数:24  
标签:tarjan int stk dfn low include

一、缩点

题目链接

https://www.luogu.com.cn/problem/P3387

题目大意

image

题目思路

缩点 + 拓扑序 + dp

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<set>
#define pi pair<int,int>
const int N = 1e4 + 5,M = 1e5 + 5;
using namespace std;
int n,m;
int h[N],ne[M],e[M],idx;
int h1[N],ne1[M],e1[M],idx1;
int stk[N],in_stk[N],top;
int dfn[N],low[N],fa[N],timestamp;
int a[N];
int din[N];
pi edge[M];
int dp[N];
set<pi>s;
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void add1(int a,int b){
    e1[idx1] = b;
    ne1[idx1] = h1[a];
    h1[a] = idx1++;
}
void tarjan(int x){
    dfn[x] = low[x] = ++ timestamp;
    stk[++top] = x;in_stk[x] = 1;
    for(int i = h[x];~i;i = ne[i]){
        int y = e[i];
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }else if(in_stk[y]){
            low[x] = min(low[x],dfn[y]);
        }
    }
    if(dfn[x] == low[x]){
        int y;
        do{
            y = stk[top--];in_stk[y] = 0;
            fa[y] = x;
            if(x == y) break;
            a[x] += a[y];
        }while(true);
    }
}
int topsort(){
    queue<int>q;
    int ans = 0;
    for(int i = 1;i <= n;++i){
        if(fa[i] == i && din[i] == 0){
            q.push(i);
            dp[i] = a[i];
            ans = max(ans,dp[i]);
        }
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h1[u];~i;i = ne1[i]){
            int v = e1[i];
            dp[v] = max(dp[v],dp[u] + a[v]);
            ans = max(ans,dp[v]);
            --din[v];
            if(din[v] == 0) q.push(v);
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    for(int i = 1;i <= m;++i){
        int x,y;scanf("%d%d",&x,&y);add(x,y);
        edge[i] = {x,y};
    }
    for(int i = 1;i <= n;++i){
        if(!dfn[i]) tarjan(i);
    }
    memset(h1,-1,sizeof(h1));
    for(int i = 1;i <= m;++i){
        int x = fa[edge[i].first],y = fa[edge[i].second];
        if(x != y && !s.count({x,y})){
            add1(x,y);
            ++din[y];
            s.insert({x,y});
        }
    }
    printf("%d",topsort());
    return 0;
}

标签:tarjan,int,stk,dfn,low,include
From: https://www.cnblogs.com/gebeng/p/18137438

相关文章

  • Tarjan 求双连通分量(点双连通分量、边双连通分量)
    注意:本文只针对无向图。对于无向图,显然不能只考虑简单的连通关系,应该研究一些更强的连通关系:双连通。前置芝士点双连通分量:若一个连通分量任意两点间都存在至少两条不经过(除起点和终点外)相同点的路径,我们就称这个连通分量为点双连通分量。边双连通分量:同理,若一个连通分量......
  • tarjan
    桥定义:删除这条边后连通块数量加1思考先暴力搜出一棵树,然后对于每一条非树边都会构成一个环,这个环上的边就不可能是桥了(拿样例来看)\(1\rightarrow2\)和\(5\rightarrow6\)就是桥假如用\(lca\)来维护加一个树上差分码量就有点惊人了考虑优化如果搜树的顺序改为\(df......
  • Tarjan板子
    Tarjan画图必备强连通分量(有向边)常见题建好有向图找强连通分量,同时记录每个强连通分量中节点的个数找节点个数最小的强连通分量点击查看代码structEdge{ intto,next;}edge[N];voidadd(intu,intv){ edge[++cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;......
  • Tarjan 算法——图论学习笔记
    Part.1引入在图论问题中,我们经常去研究一些连通性问题,比如:有向图的联通性:传递闭包——Floyd算法;有向图连通性的对称性:强联通分量(SCC)——Tarjan算法缩点;无向图的联通性:并查集;无向图的关键边:桥(割边)、边双——Tarjan算法缩点;无向图的关键点:割点、点双——Tarjan建立圆方......
  • 2024.3.23 笔记(Tarjan)
    P3469[POI2008]BLO-Blockade根据割点的定义,若节点\(i\)不是割点,则把节点\(i\)关联的所有边去掉之后,只有\(i\)与其他\(n-1\)个节点不连通,而其他\(n-1\)个节点之间是连通的。注意:题目求的是有序点对,即\((x,y)\)和\((y,x)\)算不同的点对,故此时答案是\(2*(n......
  • AcWing 1171. 距离 Tarjan算法离线求LCA
    题目输入样例1:22121001221输出样例1: 100100输入样例2:32121031151232输出样例2: 1025LCA算法:LCA(LeastCommonAncestors)最近公共祖先Tarjan求LCA是一种离线的算法,也就是说它一遍求出所有需要求的点的LCA,而不是需要求哪两个点再去求......
  • Tarjan整理
    求强连通分量个数#include<iostream>#include<cstdio>#include<stack>usingnamespacestd;structsss{ intt,ne;}e[1000005];inth[1000005],cnt;voidadd(intu,intv){ e[++cnt].ne=h[u]; e[cnt].t=v; h[u]=cnt;}intdfn[1000005],......
  • tarjan模板
    信息传递题目描述tarjan模板点击查看代码voidtarjan(intx){ dfn[x]=low[x]=++num; stk.push(x); v[x]=1; for(inti=h[x];i;i=nxt[i]) { if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } elseif(v[to[i]]) { low[x]=min(lo......
  • tarjan 各类板子集合
    tarjan大板子(非讲解):1、普通缩点DGAvoidtarjan(intx){ dfn[x]=low[x]=++cntp; q.push(x);v[x]=1; for(inti=head[x];i;i=bi[i].next){ intj=bi[i].to; if(!dfn[j]){ tarjan(j); low[x]=min(low[x],low[j]); } elseif(v[j])low[x]=min(low[x],dfn[j]); }......
  • tarjan模板
    因ppt太水遂有此文有向图求强连通分量点击查看代码voidtarjan(intx){ dfn[x]=low[x]=++num; stk.push(x); f[x]=1; for(inti=head[x];i;i=net[i]) { if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } elseif(f[to[i]]) { l......