Tarjan缩点割点(模板)

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

给定一个

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn=10009;
int n,m,p[maxn],dp[maxn];
struct edge{
    int u,to,nxt;
}d[maxn*10];int head[maxn*10],cnt=1;
void add(int u,int v){
    d[cnt].u=u,d[cnt].to=v,d[cnt].nxt=head[u],head[u]=cnt++;
}
int dfn[maxn],low[maxn],id,stack[maxn],vis[maxn],top,sd[maxn];//为tarjan准备 
void tarjan(int now)
{
    dfn[now]=low[now]=++id;
    stack[++top]=now,vis[now]=1;
    for(int i=head[now];i;i=d[i].nxt)
    {
        int w=d[i].to;
        if(!dfn[w])    
            tarjan(w),low[now]=min(low[now],low[w]);
        else if(vis[w])
            low[now]=min(low[now],low[w]);    
    }
    if(low[now]==dfn[now])
    {
        int temp;
        while(temp=stack[top--])
        {
            sd[temp]=now;
            vis[temp]=0;
            if(temp==now)    break;
            p[now]+=p[temp];//集中在now这个超级点上 
        }
    }
} 
int indug[maxn];
vector<int>vec[maxn];
int tuopu()
{
    queue<int>q;
    for(int i=1;i<=n;i++)    if(!indug[i]&&sd[i]==i)    q.push(i),dp[i]=p[i];
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=0;i<vec[now].size();i++)
        {
            int w=vec[now][i];
            dp[w]=max(dp[w],dp[now]+p[w]);
            if(--indug[w]==0)    q.push(w);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)    ans=max(ans,dp[i]);
    return ans;
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)    cin>>p[i];//读入点权
    for(int i=1;i<=m;i++)
    {
        int l,r;cin>>l>>r;
        add(l,r);    
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])    tarjan(i);
    for(int i=1;i<=m;i++)
    {
        int x=sd[d[i].u],y=sd[d[i].to];//看看两头是否是连通分量
        if(x!=y)//不是就建边 
            vec[x].push_back(y),indug[y]++;
    }
    cout<<tuopu();
    return 0;
}

还有割点的

为什么（“low[v]>=dfn[u]，此时u就是割点”）？？

因为后面的点无法回到u点之前

u就把两个部分分开来了

#include <bits/stdc++.h>
using namespace std;
const int maxn=200009;
struct edge{
    int nxt,to;
}d[maxn];
int n,m,id,cnt=1,ttp;
int head[maxn],dfn[maxn],low[maxn],cut[maxn];
void add(int u,int v){
    d[cnt].to=v,d[cnt].nxt=head[u],head[u]=cnt++;
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++id;
    int child=0;
    for(int i=head[u];i;i=d[i].nxt)
    {
        int w=d[i].to;
        if(!dfn[w])
        {
            tarjan(w,fa);
            low[u]=min(low[u],low[w]);
            if(low[w]>=dfn[u]&&u!=fa)//通过非非节点更新的low[w]
            //因为在本连通块能回溯最多到dfn[u] 
                cut[u]=1;
            if(u==fa)    child++;
        }
        low[u]=min(low[u],dfn[w]);
    }
    if(child>=2&&u==fa)    cut[u]=1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        add(l,r);add(r,l);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])    tarjan(i,i);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(cut[i])    ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        if(cut[i])
            cout<<i<<" ";
    return 0; 
}

View Code