Tarjan强联通分量学习笔记

发表于 | 更新于 | 阅读次数：

前言

一开始看到Tarjan我是拒绝的，觉得自己太菜了，肯定学不会，但是今天作业题要用到Tarjan，我只好硬着头皮学了，但是放心，这很简单

作用

Tarjan用来缩环上的点，这样图就会变成一个DAG，于是DP和最短路什么就可以乱搞了

过程

Tarjan是基于DFS序的一个算法，定义dfn为搜索时间戳，low为节点i即其子树中最小的dfn值。

那么也就是说，在一个环中，low值是一样的，而这个dfn值与low值相等的那个点就是搜索时的根，于是，这个点与栈顶到自身的所有点构成强联通分量。

例题：洛谷P3387

题目描述

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

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

输入格式：

第一行，n,m

第二行，n个整数，依次代表点权

第三至m+2行，每行两个整数u,v，表示u->v有一条有向边

输出格式：

共一行，最大的点权之和。

Sampleinput

1
2
3
4
2 2
1 1
1 2
2 1

Sampleout

1
2

对于这道题直接用Tarjan将所有强联通分量缩成一个点，因为走所有点显然更优（点权不为负）。

那么重构图就变成了一个DAG，我们直接记搜，求出子节点转移过来的最大贡献，向后dfs就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

inline void read(int &x)
{
    x=0;
    char ch=getchar();
    int pd=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            pd=-pd;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=pd;
}
inline void write(const int &x)
{
    char ggg[10001];
    int s=0;
    int tmp=x;
    if(tmp==0)
    {
        putchar('0');
        return;
    }
    if(tmp<0)
    {
        tmp=-tmp;
        putchar('-');
    }
    while(tmp>0)
    {
        ggg[s++]=tmp%10+'0';
        tmp/=10;
    }
    while(s>0)
    {
        putchar(ggg[--s]);
    }
}
const int N=1e4+30;
struct dd
{
    int begin,end,nt;
}e1[200010],e2[200020];
int t1,t2,h1[N],h2[N],dfn[N],low[N],ans,cnt,id[N];
int bh,v[N],a[N],f[N],m,n;
void add1(int begin,int end)
{
    ++t1;
    e1[t1].begin=begin;
    e1[t1].end=end;
    e1[t1].nt=h1[begin];
    h1[begin]=t1;
}
void add2(int begin,int end)
{
    ++t2;
    e2[t2].begin=begin;
    e2[t2].end=end;
    e2[t2].nt=h2[begin];
    h2[begin]=t2;
}
stack <int >st;
void tarjan(int x)
{
    dfn[x]=low[x]=++bh;
    st.push(x);
    for(register int i=h1[x];i;i=e1[i].nt)
    {
        int u=e1[i].end;
        if(!dfn[u])
        {
            tarjan(u);
            low[x]=min(low[x],low[u]);
        }
        else
        {
            if(!id[u])
            {
                low[x]=min(low[x],dfn[u]);
            }
        }
    }
    if(dfn[x]==low[x])
    {
        id[x]=++cnt;
        v[cnt]+=a[x];
        while(st.top()!=x)
        {
            id[st.top()]=cnt;
            v[cnt]+=a[st.top()];
            st.pop();
        }
        st.pop();
    }
}

void dfs(int x,int fa)
{
    f[x]=v[x];
    int gg=-100000;
    for(register int i=h2[x];i;i=e2[i].nt)
    {
        int u=e2[i].end;
        if(u==fa)continue;
        dfs(u,x);
        gg=max(gg,f[u]);
    }
    f[x]+=(gg==-100000?0:gg);
}
int main()
{
    read(n);
    read(m);
    for(register int i=1;i<=n;++i)
    {
        read(a[i]);
    }
    for(register int i=1;i<=m;++i)
    {
        int xx,yy;
        read(xx);
        read(yy);
        add1(xx,yy);
    }
    for(register int i=1;i<=n;++i)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(register int i=1;i<=t1;++i)
    {
        if(id[e1[i].begin]!=id[e1[i].end])
        {
            add2(id[e1[i].begin],id[e1[i].end]);
        }
    }
    for(register int i=1;i<=cnt;++i)
    {
        if(!f[i])
        {
            dfs(i,0);
        }
        ans=max(ans,f[i]);
    }
    write(ans);
}