Tarjan 算法
先是废话时间: 说来挺惭愧 , 好几个月以前就学过 tarjan 算法然而现在才第一次写
模板题:[luogu P3387][模板] 缩点 https://www.luogu.org/problem/P3387
tarjan 缩点 & dp
为啥要缩点答案显然
把环缩成一个点
然后图上拓扑 dp
tarjan 同名算法有很多 , 比如本 blog 的缩点与割点的 tarjan 算法其实并不是一个东西 , 但是很是相似
这个 tarjan , 需要三个东西
第一: 一个栈来存放搜到的点
第二: 一个时间戳 dfn , 表示第几个搜到这个点的
第三: low 数组 , 表示够追溯到的最早的栈中节点的次序号
首先 , 初始化的时候肯定有
1 dfn[now] = low[now] = ++Index
然后开始遍历边
如果遍历到的点没有碰过
那么递归 tarjan
递归结束后
1 low[now] = std::min(low[now], low[to]);
那么如果下一个点已经去过了呐
那么就不用递归了
1 low[now] = std::min(low[now], dfn[to]);
为什么是 dfn 呢?
照我的理解 , 应该是如果直接用 low 说不定会跳到这个环以外的地方
不过这个缩点 tarjan 里面把 dfn 换成 low 是可以的 , 但是一会的割点 tarjan 就不可以了
当最后时一个点的 low == dfn , 那个这个点注定是一个缩点之后仍然存留在图上的一个点
那么就可以快落缩点了 , 把栈里的元素不停的向外弹就是了
然后根据题目性质拓扑 dp , 没了
- #include<cmath>
- #include<queue>
- #include<stack>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<iostream>
- #include<algorithm>
- #define APART puts("----------------------")
- #define debug 1
- #define FILETEST 0
- #define inf 100010
- #define ll long long
- #define ha 998244353
- #define INF 0x7fffffff
- #define INF_T 9223372036854775807
- #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
- namespace chino{
- inline void setting(){
- #if FILETEST
- freopen("test.in", "r", stdin);
- freopen("test.me.out", "w", stdout);
- #endif
- return;
- }
- inline int read(){
- char c = getchar(), up = c; int num = 0;
- for(; c <'0' || c> '9'; up = c, c = getchar());
- for(; c>= '0' && c <= '9'; num = (num <<3) + (num << 1) + (c ^ '0'), c = getchar());
- return up == '-' ? -num : num;
- }
- int n, m;
- int ans;
- int cntE, cntR, cntJ;
- int val[inf], dp[inf];
- int vis[inf], in[inf];
- int belong[inf], dfn[inf], low[inf];
- int head[inf], rehead[inf];
- struct Edge{
- int to;
- int from;
- int next;
- }e[inf << 1], r[inf << 1];
- std::queue <int> Q;
- std::stack <int> S;
- inline void AddEdge(int from, int to, int &cntE, int *head, Edge *e){
- ++cntE;
- e[cntE].from = from;
- e[cntE].to = to;
- e[cntE].next = head[from];
- head[from] = cntE;
- return;
- }
- void tarjan(int now){
- low[now] = dfn[now] = ++cntJ;
- vis[now] = 1;
- S.push(now);
- for(int i = head[now]; i; i = e[i].next){
- int to = e[i].to;
- if(dfn[to] == 0){
- tarjan(to);
- low[now] = std::min(low[now], low[to]);
- } else if(vis[to])
- low[now] = std::min(low[now], dfn[to]);
- }
- if(low[now] == dfn[now]){
- int top = S.top();
- while(1){
- top = S.top();
- S.pop();
- belong[top] = now;
- vis[top] = 0;
- if(top == now)
- break;
- val[now] += val[top];
- }
- }
- return;
- }
- inline void topoDP(){
- while(!Q.empty())
- Q.pop();
- for(int i = 1; i <= n; i++){
- if(belong[i] == i && in[i] == 0)
- Q.push(i), dp[i] = val[i];
- }
- while(!Q.empty()){
- int x = Q.front();
- Q.pop();
- for(int i = rehead[x]; i; i = r[i].next){
- int to = r[i].to;
- dp[to] = std::max(dp[to], dp[x] + val[to]);
- --in[to];
- if(in[to] == 0)
- Q.push(to);
- }
- }
- return;
- }
- inline int main(){
- n = read();
- m = read();
- for(int i = 1; i <= n; i++)
- val[i] = read();
- for(int i = 1; i <= m; i++){
- int u = read();
- int v = read();
- AddEdge(u, v, cntE, head, e);
- }
- for(int i = 1; i <= n; i++){
- if(dfn[i] == 0)
- tarjan(i);
- }
- for(int i = 1; i <= m; i++){
- int u = belong[e[i].from];
- int v = belong[e[i].to];
- if(u == v)
- continue;
- AddEdge(u, v, cntR, rehead, r);
- ++in[v];
- }
- topoDP();
- for(int i = 1; i <= n; i++)
- ans = std::max(ans, dp[i]);
- printf("%d\n", ans);
- return 0;
- }
- }//namespace chino
- int main(){return chino::main();}
复杂度 O(n+m)
下一题: P3388 [模板] 割点 (割顶) https://www.luogu.org/problem/P3388
说在前面 , 这道题是无向边 , 上一题是有向边
而割点的定义是:
在无向连通图中, 如果将其中一个点以及所有连接该点的边去掉, 图就不再连通, 那么这个点就叫做割点 (cut vertex / articulation point).
举例 , 这张图 5 点就是割点
求割点, 也是一个叫做 tarjan 的算法
首先每次搜索时确定一个根节点 , 判断根节点是不是割点很简单 , 看看子树的数量是不是大于等于 2 就可以了
那么非根节点呢?
遍历的时候检测一下是不是所到的点的 low 大于等于当前点的 dfn 就可以了
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<iostream>
- #include<algorithm>
- #define APART puts("----------------------")
- #define debug 1
- #define FILETEST 0
- #define inf 100010
- #define ll long long
- #define ha 998244353
- #define INF 0x7fffffff
- #define INF_T 9223372036854775807
- #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
- namespace chino{
- inline void setting(){
- #if FILETEST
- freopen("test.in", "r", stdin);
- freopen("test.me.out", "w", stdout);
- #endif
- return;
- }
- inline int read(){
- char c = getchar(), up = c; int num = 0;
- for(; c <'0' || c> '9'; up = c, c = getchar());
- for(; c>= '0' && c <= '9'; num = (num <<3) + (num << 1) + (c ^ '0'), c = getchar());
- return up == '-' ? -num : num;
- }
- int n, m;
- int cntE, cntA, cntJ;
- int low[inf], dfn[inf];
- int cut[inf];
- int head[inf];
- struct Edge{
- int to;
- int next;
- }e[inf << 1];
- inline void AddEdge(int from, int to){
- ++cntE;
- e[cntE].to = to;
- e[cntE].next = head[from];
- head[from] = cntE;
- return;
- }
- void tarjan(int now, int root){
- low[now] = dfn[now] = ++cntJ;
- int tmp = 0;
- for(int i = head[now]; i; i = e[i].next){
- int to = e[i].to;
- if(dfn[to] == 0){
- tarjan(to, 0);
- low[now] = std::min(low[now], low[to]);
- if(low[to]>= dfn[now] && root == 0)
- cut[now] = 1;
- if(root)
- ++tmp;
- } else low[now] = std::min(low[now], dfn[to]);
- }
- if(root && tmp>= 2)
- cut[now] = 1;
- return;
- }
- inline int main(){
- n = read();
- m = read();
- for(int i = 1; i <= m; i++){
- int u = read();
- int v = read();
- AddEdge(u, v);
- AddEdge(v, u);
- }
- for(int i = 1; i <= n; i++){
- if(dfn[i] == 0)
- tarjan(i, 1);
- }
- for(int i = 1; i <= n; i++){
- if(cut[i])
- ++cntA;
- }
- printf("%d\n", cntA);
- for(int i = 1; i <= n; i++){
- if(cut[i])
- printf("%d", i);
- }
- return 0;
- }
- }//namespace chino
- int main(){return chino::main();}
来源: http://www.bubuko.com/infodetail-3198290.html