2.17学习总结

tarjan

【模板】缩点https://www.luogu.com.cn/problem/P3387

题目描述

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

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

输入格式

第一行两个正整数 �,�n,m

第二行 �n 个整数，其中第 �i 个数 ��ai​ 表示点 �i 的点权。

第三至 �+2m+2 行，每行两个整数 �,�u,v，表示一条 �→�u→v 的有向边。

输出格式

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

输入输出样例

输入 #1复制

2 2
1 1
1 2
2 1

输出 #1复制

2

说明/提示

对于 100%100% 的数据，1≤�≤1041≤n≤104，1≤�≤1051≤m≤105，0≤��≤1030≤ai​≤103。

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x& - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N=1e5+5;struct edge{int from;int to;int next;
}e[N],e1[N];int instack[N];
int s,tot,dfn[N],low[N],head[N],sd[N],dis[N],w[N],m,n,in[N],h[N],sum;
stack<int>st;void add(int u,int v){e[++tot].from=u;e[tot].to=v;e[tot].next=head[u];head[u]=tot;
}void tarjan(int u){dfn[u]=low[u]=++s;st.push(u);instack[u]=1;for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if (instack[v]){low[u]=min(low[u],dfn[v]);}}if (dfn[u]==low[u]){while (!st.empty()){int p=st.top();st.pop();instack[p]=0;sd[p]=u;if (u==p) break;w[u]+=w[p];}}
} int topo(){queue<int>q;for (int i=1;i<=n;++i){if (!in[i] && sd[i]==i){q.push(i);dis[i]=w[i];}}while (!q.empty()){int u=q.front(); q.pop();for (int i=h[u];i;i=e1[i].next){int v=e1[i].to;dis[v]=max(dis[v],dis[u]+w[v]);in[v]--;if (in[v]==0) q.push(v);}}int ans=0;for (int i=1;i<=n;++i){ans=max(ans,dis[i]);}return ans;
}signed main(){cin>>n>>m;for (int i=1;i<=n;++i) cin>>w[i];for (int i=1;i<=m;++i){int u,v;cin>>u>>v;add(u,v);}for (int i=1;i<=n;++i){if (!dfn[i]){tarjan(i);}}for (int i=1;i<=m;++i){int x=sd[e[i].from],y=sd[e[i].to];if (x!=y){e1[++sum].from=x;e1[sum].to=y;e1[sum].next=h[x];h[x]=sum;in[y]++;}}cout<<topo();
}

模板】割点（割顶）https://www.luogu.com.cn/problem/P3388#submit

题目背景

割点

题目描述

给出一个 �n 个点，�m 条边的无向图，求图的割点。

输入格式

第一行输入两个正整数 �,�n,m。

下面 �m 行每行输入两个正整数 �,�x,y 表示 �x 到 �y 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

输入输出样例

输入 #1复制

6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6

输出 #1复制

1
5

说明/提示

对于全部数据，1≤�≤2×1041≤n≤2×104，1≤�≤1×1051≤m≤1×105。

点的编号均大于 00 小于等于 �n。

tarjan图不一定联通。

#include <bits/stdc++.h>
using namespace std;const int N=2e5+5,M=1e6;struct edge{int from;int to;int next;
}e[M];int s,dfn[N],low[N],head[N],n,m,tot,cut[N];void add(int u,int v){e[++tot].from=u;e[tot].to=v;e[tot].next=head[u];head[u]=tot;
}
void tarjan(int u,int fa){dfn[u]=low[u]=++s;int child=0;for (int i=head[u];i;i=e[i].next){int v=e[i].to;if (!dfn[v]){tarjan(v,fa);low[u]=min(low[u],low[v]);if (dfn[u]<=low[v] && u!=fa){cut[u]=1;}if (u==fa){child++;}}low[u]=min(low[u],dfn[v]);}if (u==fa && child>=2){cut[u]=1;}
}
int main(){cin>>n>>m;for (int i=0;i<m;++i){int u,v;cin>>u>>v;add(u,v);add(v,u);}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<<" ";}
}