跟3352一模一样,不过,需加判重。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,r; #define maxn 5005 bool map[maxn][maxn]; class node { public: int to,next; }; node g[maxn*5]; int head[maxn],cnt; int dfn[maxn],low[maxn],du[maxn]; void add(int u,int v) { g[++cnt].to =v; g[cnt].next =head[u]; head[u]=cnt; } void dfs(int u,int fa) { dfn[u]=low[u]=++cnt; int i; for(i=head[u];i;i=g[i].next ) { int v=g[i].to; if(!dfn[v]) { dfs(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa) { low[u]=min(low[u],dfn[v]); } } } void solve() { int i,j,ans=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); cnt=0; dfs(1,-1); memset(du,0,sizeof(du)); for(i=1;i<=n;i++) { for(j=head[i];j;j=g[j].next ) { int v=g[j].to; if(low[i]!=low[v]) du[low[i]]++;//low值相同的节点即在一个双联通分量里 } } for(i=1;i<=n;i++) { // printf("%d ",du[i]); if(du[i]==1)ans++; } //printf("\n"); // for(i=1;i<=n;i++) // printf("%d ",low[i]); //printf("\n"); printf("%d\n",(ans+1)/2); } int main() { int a,b; while(scanf("%d%d",&n,&r)!=EOF) { cnt=0; memset(map,0,sizeof(map)); while(r--) { scanf("%d%d",&a,&b); if(!map[a][b]) { add(a,b); add(b,a); map[a][b]=map[b][a]=1; } } solve(); } return 0; }
您还没有登录,请您登录后再发表评论
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
7. **图的割边和割点**:分析图的连接性和关键边点,如POJ3352。 8. **最小割模**:寻找图中的最小割,通常用于优化问题。 以上就是POJ平台中涉及到的一些基础和进阶算法及其相关的编程题目,这些知识对于提升编程...
c表示有多少种珍珠 ai 表示第i种珍珠所需的数量 pi 表示第i种珍珠的价钱 每买一种珍珠都需要付额外的10 * pi的钱,便宜的珍珠可以用贵的珍珠来代替,求最少的钱的总数。
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
最小割推荐题目源码主要涉及图论中的一个重要概念——最小割问题,以及它在解决推荐系统问题中的应用。最小割问题通常与网络流问题密切相关,是计算机科学领域中图算法的一种经典应用。在这个主题中,我们主要关注...
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中...这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
【标题】"POJ1942-Paths on a Grid"是北京大学在线编程平台POJ上的一道经典算法题目,其主要目标是探索在网格上行走的路径问题。 【描述】该题目的描述中提到“解题报告+AC代码”,这暗示了解决此问题的关键在于...
POJ3177 - Redundant Paths - **题目链接**:[POJ3177](http://acm.pku.edu.cn/JudgeOnline/problem?) - **解法概述**:这是一道关于冗余路径的问题,可以通过拓扑排序或动态规划的方法求解。 - **拓扑排序 / ...
### POJ2485Highways —— JAVA版 #### 题目背景与目标 在虚拟的岛国Flatopia中,尽管地形平坦,但该国却没有一条公共高速公路,这导致了交通上的不便。为了解决这个问题,Flatopia政府计划修建一些高速公路,使得...
在POJ2914题中,提供了Stoer-Wagner 算法的实现代码,该代码使用C++语言编写,使用prim算法计算图的最小割,并输出图的全局最小割结果。 Stoer-Wagner 算法是一种常用的算法,用于计算图的全局最小割,该算法可以...
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
最小割问题的目标是在图中找到一个分割,使得一边包含源点,另一边包含汇点,同时这个分割的边的总容量最小。这个问题可以转化为寻找最大流问题来解决,因为在一个有向图中,最大流的值等于最小割的容量。 在描述的...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,一个无向图的最小生成树是指连接所有顶点的一棵树,其边的权重之和尽可能小。解决这类问题的常见算法有Prim算法...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
相关推荐
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
7. **图的割边和割点**:分析图的连接性和关键边点,如POJ3352。 8. **最小割模**:寻找图中的最小割,通常用于优化问题。 以上就是POJ平台中涉及到的一些基础和进阶算法及其相关的编程题目,这些知识对于提升编程...
c表示有多少种珍珠 ai 表示第i种珍珠所需的数量 pi 表示第i种珍珠的价钱 每买一种珍珠都需要付额外的10 * pi的钱,便宜的珍珠可以用贵的珍珠来代替,求最少的钱的总数。
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
最小割推荐题目源码主要涉及图论中的一个重要概念——最小割问题,以及它在解决推荐系统问题中的应用。最小割问题通常与网络流问题密切相关,是计算机科学领域中图算法的一种经典应用。在这个主题中,我们主要关注...
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中...这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
【标题】"POJ1942-Paths on a Grid"是北京大学在线编程平台POJ上的一道经典算法题目,其主要目标是探索在网格上行走的路径问题。 【描述】该题目的描述中提到“解题报告+AC代码”,这暗示了解决此问题的关键在于...
POJ3177 - Redundant Paths - **题目链接**:[POJ3177](http://acm.pku.edu.cn/JudgeOnline/problem?) - **解法概述**:这是一道关于冗余路径的问题,可以通过拓扑排序或动态规划的方法求解。 - **拓扑排序 / ...
### POJ2485Highways —— JAVA版 #### 题目背景与目标 在虚拟的岛国Flatopia中,尽管地形平坦,但该国却没有一条公共高速公路,这导致了交通上的不便。为了解决这个问题,Flatopia政府计划修建一些高速公路,使得...
在POJ2914题中,提供了Stoer-Wagner 算法的实现代码,该代码使用C++语言编写,使用prim算法计算图的最小割,并输出图的全局最小割结果。 Stoer-Wagner 算法是一种常用的算法,用于计算图的全局最小割,该算法可以...
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
最小割问题的目标是在图中找到一个分割,使得一边包含源点,另一边包含汇点,同时这个分割的边的总容量最小。这个问题可以转化为寻找最大流问题来解决,因为在一个有向图中,最大流的值等于最小割的容量。 在描述的...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
这个题目主要涉及图论中的一个经典算法问题——最小生成树(Minimum Spanning Tree, MST)。在图论中,一个无向图的最小生成树是指连接所有顶点的一棵树,其边的权重之和尽可能小。解决这类问题的常见算法有Prim算法...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573