POJ–3352 道路建设
题目描述
输入样例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
输出样例1
2
输入样例2
3 3 1 2 2 3 1 3
输出样例2
0
题意分析:
景点就是图中的点,道路就是路径.题目要求任何道路建设过程中,仍然可以使用其他道路保证道路两边的景点仍然可以到达.在一个边双联通分量中,任意两个点之间存在两条以及以上的路径.我们这个题就是得构建双联通分量.
当我们运行Tarjan算法后,相同的双联通分量会有一个相同的low值,而且对于一个双联通分量来说,low值对应的就是第一次遍历到该连通分量的标号. 我们可以把这些双连通分量进行缩点,然后这就形成了一个树,如下图所示.然后我们统计叶子的个数,然后每两个叶子形成一条边,这样就形成了一条新的回路.树也就成了一个双联通图.
解题步骤
运行Tarjan算法求解双连通分量
样例1中,可求得边连通分量共有4个.样例2中双联通分量只有一个(所以需要添加0条边).
将每个双连通分量缩成点.
计算需要的添加的新路数量.如果叶子数为k,则至少添加(k+1)/2边。例如,3个度为1的顶点,需要加两条边,4个度为1的顶点也需要加两条边。因为对于奇数个叶子节点,每两个需要一条边来构成双连通分量.也就是需要(k+1) / 2条边.如果偶数个点.则需要 k /2. 易知 k+1 / 2 与k/2值是一样的.所以都用k+1/2即可
疑惑点:
算法设计
参考代码
#include<iostream> using namespace std; const int maxn = 1000+10; int head[maxn],num,vis[maxn],dfn[maxn],low[maxn],cnt,degree[maxn],leaf;//num:用于edge下标的控制 ,cnt:用于dfn的标号 struct Edge{ int next,to; }e[maxn * maxn]; void add(int u,int v){ e[++num].next = head[u]; e[num].to = v; head[u] = num; } void tanjar(int u,int fa){ dfn[u] = low[u] = ++cnt; for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(v==fa){ continue; } if(!dfn[v]){ tanjar(v,u); low[u] = min(low[u],low[v]); }else{ low[u] = min(low[u],low[v]); } } } int main() { int n,m,u,v; cin>>n>>m; while(m--){ cin>>u>>v; add(u,v); add(v,u); } tanjar(1,0); for(int u = 1; u <= n; u++){//缩点 for(int j = head[u]; j; j =e[j].next ){ int v = e[j].to; if(low[u]!=low[v]){ degree[low[u]]++; } } } for(int i = 1;i <= n; i++){ if(degree[i]==1){ leaf++; } } cout<<(leaf+1)/2<<endl; return 0; }