wordpress 全站pjax,在线做试卷的网站,114网站制作,沈阳网站建设服务电话tarjan
【模板】缩点https://www.luogu.com.cn/problem/P3387 题目描述 给定一个 #xfffd;n 个点 #xfffd;m 条边有向图#xff0c;每个点有一个权值#xff0c;求一条路径#xff0c;使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者…tarjan
【模板】缩点https://www.luogu.com.cn/problem/P3387 题目描述 给定一个 n 个点 m 条边有向图每个点有一个权值求一条路径使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点但是重复经过的点权值只计算一次。 输入格式 第一行两个正整数 ,n,m 第二行 n 个整数其中第 i 个数 ai 表示点 i 的点权。 第三至 2m2 行每行两个整数 ,u,v表示一条 →u→v 的有向边。 输出格式 共一行最大的点权之和。 输入输出样例 输入 #1复制 2 2 1 1 1 2 2 1 输出 #1复制 2 说明/提示 对于 100%100% 的数据1≤≤1041≤n≤1041≤≤1051≤m≤1050≤≤1030≤ai≤103。 #include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N1e55;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;
stackintst;void add(int u,int v){e[tot].fromu;e[tot].tov;e[tot].nexthead[u];head[u]tot;
}void tarjan(int u){dfn[u]low[u]s;st.push(u);instack[u]1;for (int ihead[u];i;ie[i].next){int ve[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 pst.top();st.pop();instack[p]0;sd[p]u;if (up) break;w[u]w[p];}}
} int topo(){queueintq;for (int i1;in;i){if (!in[i] sd[i]i){q.push(i);dis[i]w[i];}}while (!q.empty()){int uq.front(); q.pop();for (int ih[u];i;ie1[i].next){int ve1[i].to;dis[v]max(dis[v],dis[u]w[v]);in[v]--;if (in[v]0) q.push(v);}}int ans0;for (int i1;in;i){ansmax(ans,dis[i]);}return ans;
}signed main(){cinnm;for (int i1;in;i) cinw[i];for (int i1;im;i){int u,v;cinuv;add(u,v);}for (int i1;in;i){if (!dfn[i]){tarjan(i);}}for (int i1;im;i){int xsd[e[i].from],ysd[e[i].to];if (x!y){e1[sum].fromx;e1[sum].toy;e1[sum].nexth[x];h[x]sum;in[y];}}couttopo();
}模板】割点割顶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×1041≤≤1×1051≤m≤1×105。 点的编号均大于 00 小于等于 n。 tarjan图不一定联通。 #include bits/stdc.h
using namespace std;const int N2e55,M1e6;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].fromu;e[tot].tov;e[tot].nexthead[u];head[u]tot;
}
void tarjan(int u,int fa){dfn[u]low[u]s;int child0;for (int ihead[u];i;ie[i].next){int ve[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 (ufa){child;}}low[u]min(low[u],dfn[v]);}if (ufa child2){cut[u]1;}
}
int main(){cinnm;for (int i0;im;i){int u,v;cinuv;add(u,v);add(v,u);}for (int i1;in;i){if (!dfn[i]) tarjan(i,i);}int ans0;for (int i1;in;i){if (cut[i]) ans;}coutansendl;for (int i1;in;i){if (cut[i])couti ;}
}
