poj 3177 Path Redundancy (边双连通图的性质及点收缩)
发布时间
阅读量：
阅读量
题目要求：提供一个图，包含若干顶点与边，需要计算至少需添加多少条边，才能使该图转变为边双连通的结构。
算法竞赛进阶指南中图论练习题14
1、采用边双连通的Tarjan算法进行处理，并对所得结果进行缩点操作。
2、int degree[MaxN]; // degree[i] 表示第i个边双连通分量的入度数值
3、计算所有边双连通分量的缩点后，统计其中度数degree[i]等于1的缩点数量sum。最终的答案为 (sum + 1) / 2。这些度数为1的节点之间进行配对，使得每对节点之间形成闭合回路，从而确保整个图达到边双连通的状态。
#include <cstdio>
#include <stack>
using namespace std;
const int MaxN = 5e3 + 10;
const int MaxM = 2e4 + 10;
int head[MaxN], ver[MaxM], Next[MaxM];
int dfn[MaxN], low[MaxN], n, m, tot, num;
bool bridge[MaxM];
int dcc[MaxN], cnt; //边双连通字块的编号， 数量
int degree[MaxN]; // degree[i] 表示第i块全部评论 (0)
还没有任何评论哟~