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 0x3f3f3f3f3f3f3f3f
const 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<<" ";
}
}原文地址：https://blog.csdn.net/2301_80489323/article/details/136143237
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！