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<<" ";}
}