模板网站的建设,四川网站建设哪家好,新手建站论坛,应用商店下载描述 现在几乎是夏天#xff0c;这意味着几乎是夏天的施工时间#xff01;今年#xff0c;负责偏远岛热带岛屿天堂道路的好心人希望修复和升级岛上各个旅游景点之间的各种道路。 道路本身也很有趣。由于岛上的奇怪风俗#xff0c;道路的安排使得它们不会在交叉路口相遇这意味着几乎是夏天的施工时间今年负责偏远岛热带岛屿天堂道路的好心人希望修复和升级岛上各个旅游景点之间的各种道路。 道路本身也很有趣。由于岛上的奇怪风俗道路的安排使得它们不会在交叉路口相遇而是通过桥梁和隧道相互交叉或下方。通过这种方式每条道路在两个特定的旅游景点之间穿行这样游客就不会无法挽回地迷路。 不幸的是考虑到每条道路所需的维修和升级的性质当建筑公司在某条道路上施工时这条道路在任何方向都无法使用。如果无法在两个旅游景点之间旅行即使建筑公司在任何特定时间只在一条道路上施工这可能会造成问题。 因此偏远岛屿的公路部门决定请您的咨询服务来帮助解决这个问题。已决定在各个景点之间修建新的道路以便在最终配置中如果任何一条道路正在施工则仍可以使用剩余的道路在任何两个旅游景点之间行驶。您的任务是找到所需的最少数量的新道路。
输入 第一行输入由正整数n和r组成用空格隔开其中3≤n≤1000是岛上旅游景点的数量2≤r≤1000是道路的数量。旅游景点的标记很方便从1到n。以下r行中的每一行将由两个整数v和w组成用空格隔开表示标记为v和w的景点之间存在一条道路。请注意您可以沿着每条道路向任何方向行驶任何一对旅游景点之间最多只能有一条道路直接连接。此外您可以放心在当前配置中您可以在任意两个旅游景点之间旅行。 输出 一行由一个整数组成它给出了我们需要添加的最小道路数。
Sample Input
Sample Input 1 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10
Sample Input 2 3 3 1 2 2 3 1 3 Sample Output
Output for Sample Input 1 2
Output for Sample Input 2 0 Source
CCC 2007
思路
用Tarjan算法求边双连通分量缩点每两个度为1的叶子节点添加一条边。
AC代码
#include iostream
#include cstring
#include cstdio
#include algorithm
#define AUTHOR HEX9CF
using namespace std;const int maxn 100005;int cnt;
struct Snode {int to;int next;
}edge[maxn];
int head[maxn];// tarjan
int num;
int dfn[maxn], low[maxn];
int deg[maxn];void init(){cnt 0;num 0;memset(head, -1, sizeof(head));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(deg, 0, sizeof(deg));
}void add(int u, int v){edge[cnt].to v;edge[cnt].next head[u];head[u] cnt;
}void print(int x){for(int j 1; j x; j){cout j -;for(int i head[j]; ~i; i edge[i].next){cout edge[i].to;}cout endl;}
}void tarjan(int u, int root){dfn[u] low[u] num;for (int i head[u]; ~i; i edge[i].next){int v edge[i].to;if (v root){continue;}if(!dfn[v]){tarjan(v, u);low[u] min(low[u], low[v]);}else{low[u] min(low[u], dfn[v]);}}}int main() {int n, r, si;while(cin n r){init();for(int i 0; i r; i){int u, v;cin u v;add(u, v);add(v, u);}// print(r);for(int i 1; i r; i){if(!dfn[i]){tarjan(i,i);}}// 求缩点和度for(int u 1; u n; u){for(int i head[u]; ~i; i edge[i].next){int v edge[i].to;if(low[u] ! low[v]){deg[low[u]];}}}// 统计叶子数int leaf 0;for(int i 1; i n; i){if(1 deg[i]){leaf;}}// 每两个叶子间加一条路cout (leaf 1) / 2 endl;}return 0;
}
