Tarjan SCC

Tarjan强连通分量

关于什么叫做强连通分量,简单来说就是从一张图上面的某个点出发,经过一条路径还能回到这个点,那么这个点就是一个强连通分量。

对于强连通分量的具体解释详见:维基百科 & 百度百科

给定一张有环图,所谓缩点,就是把图上的每一个强连通分量(即环)缩为一个点,使得原图变为一张无环图。

如图为一张有环图

找出图中的强连通分量

缩点后得到DAG

看一道模板题

P3387 【模板】缩点

题目要求找出图上的点权最大的路径

首先对于图上的任意强连通分量来说,假如强连通分量上面的任意一点在这条路径上,那么这个环上面的每一个点一定也在这条路径上面。

因此,我们不妨把每一个环缩为一个点,这个点的点权即为环上所有点权之和。重新建立一张DAG。

然后,找出图上点权最大的一条路。拓扑排序简单dp一下即可。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<set>
#include<algorithm>

int n,m,Time=0,cnt=0,ans=0;

using std::cerr;
using std::endl;

typedef struct EdgeNode
{
int to;
EdgeNode *next;
EdgeNode(int to,EdgeNode *nxt):to(to)
{
next=nxt;
}
~EdgeNode()
{
if(next!=nullptr)
delete next;
}
}*Edge;

struct Point
{
Edge head;
int val,in,low,dfn,belong;
bool vis;

Point()
{
head=nullptr;
dfn=low=val=in=0;
vis=false;
}
~Point()
{
if(head!=nullptr)
delete head;
}
}*pot,*DAG;

std::stack<int> stk;

void Tarjan(int pos)
{
pot[pos].dfn=pot[pos].low=++Time;
stk.push(pos);
pot[pos].vis=1;
for(Edge node=pot[pos].head;node!=nullptr;node=node->next)
{
int to=node->to;
if(!pot[to].dfn)
{
Tarjan(to);
pot[pos].low=std::min(pot[pos].low,pot[to].low);
}
else if(pot[to].vis)
pot[pos].low=std::min(pot[pos].low,pot[to].dfn);
}
if(pot[pos].dfn==pot[pos].low)
{
int now;
cnt++;
do
{
now=stk.top();
stk.pop();
pot[now].vis=0;
pot[now].belong=cnt;
}
while(now!=pos);
}
}

void rebuild()
{
std::set<std::pair<int,int> > S;
for(int i=1;i<=n;i++)
{
int from=pot[i].belong;
DAG[from].val+=pot[i].val;
for(Edge node=pot[i].head;node!=nullptr;node=node->next)
{
int to=pot[node->to].belong;
if(from!=to&&!S.count(std::make_pair(from,to)))
{
DAG[from].head=new EdgeNode(to,DAG[from].head);
DAG[to].in++;
S.insert(std::make_pair(from,to));
}
}
}
S.clear();
}

void DP()
{
int *dp=new int[cnt+10];
std::memset(dp,0,(cnt+10)*sizeof(int));
for(int i=1;i<=cnt;i++)
if(DAG[i].in==0)
{
stk.push(i);
dp[i]=DAG[i].val;
}
while(!stk.empty())
{
int from=stk.top();
stk.pop();
for(Edge node=DAG[from].head;node!=nullptr;node=node->next)
{
int to=node->to;
dp[to]=std::max(dp[to],dp[from]+DAG[to].val);
DAG[to].in--;
if(DAG[to].in==0)
stk.push(to);
}
}
for(int i=1;i<=cnt;i++)
ans=std::max(ans,dp[i]);
delete [] dp;
}

int main()
{
scanf("%d%d",&n,&m);
pot=new Point[n+10];
for(int i=1;i<=n;i++)
scanf("%d",&pot[i].val);
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
pot[u].head=new EdgeNode(v,pot[u].head);
}
for(int i=1;i<=n;i++)
if(!pot[i].dfn)
Tarjan(i);
while(!stk.empty())stk.pop();
DAG=new Point[cnt+10];
rebuild();
delete [] pot;
DP();
printf("%d\n",ans);
delete [] DAG;
return 0;
}