试统计树上一共有多少条特殊路径。
[输入格式]
+ 第一行包含一个整数N，代表节点数
+ 第二行包含N个整数p1，p2，…，pn，代表每个节点的父节点编号。若pi=0，则该节点为树的根节点
[输出数据]
输出树上一共有多少条特殊路径
[补充说明]
+ 0≤pi≤N
+ 有且仅有一个pi=0
+ 输入的图是一棵树
[样例1]
输入：
7
0 5 5 1 4 1 4
输出：
10
[样例2]
输入：
5
2 3 0 2 2
输出：
7
其中样例1的图形示例：
分析：
首先，它是一棵树，这个条件可以保证图中任意两点之间都是连通的。然后，我们要把它作为一个无向连通图来处理。这里，我们以邻接表为基本的数据结构。要找到所有特殊路径，从本质上看，就是让我们对图进行遍历。我们以从点1出发为例，每遍历到一个点，只有当这个点比路径上的初始点大时，我们才把它加入路径，另外，把它与这条路径上的大值作比较，若新增的点较大，则表示一条新的特殊路径的产生，输出这条路径上的首尾点，并更新这条路上的大点。这样，我们依次从1开始遍历（1是起始点），就可以找到所有特殊路径。关于如何保存大点的问题，可以给结构体增加一个变量，保存当前结点所在路径上的大值。
程序代码：
# include# include# define SIZE 20
# define NEWSIZE 20
using namespace std;
//以邻接表为基本数据结构
typedef struct ArcNode { //边的结点结构类型
int adjvex; //该边的终点编号
struct ArcNode* nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VexNode { //顶点结构
int data; //当前结点的值
int maxdata; //当前结点所在路径上的大值
ArcNode* firstarc; //指向第一条与该顶点有关的边的指针
}VexNode;
typedef struct Graph { //邻接表结构类型
VexNode* VNode; //定义邻接表
int vexnum; //顶点个数
int size; //邻接表的大小
}Graph;
int sum = 0; //特殊路径总数
int* Visit; //辅助数组，标记点是否已被访问过
void Create(Graph& G); //创建
void Find(Graph G); //寻找全部特殊路径
int main()
{
Graph G;
Create(G); //创建
cout<< endl;
Find(G); //寻找全部特殊路径
cout<< "特殊路径总数:"<< sum<< endl;
return 0;
}
void Create(Graph& G) //创建
{
cin >>G.vexnum; //输入顶点个数
G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
G.size = SIZE;
while (G.size< G.vexnum) {
//根据点的个数动态分配空间
G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));
G.size += NEWSIZE;
}
Visit = (int*)malloc((G.size + 10) * sizeof(int));
for (int i = 1; i<= G.vexnum; i++) {
G.VNode[i].data = i;
G.VNode[i].firstarc = NULL; //邻接表初始化，所有单向链表均为空表
}
int a;
ArcNode* p, * q;
for (int i = 1; i<= G.vexnum; i++) {
cin >>a;
if (a >0) {
p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点p
p->nextarc = NULL;
p->adjvex = i;
q = G.VNode[a].firstarc;
if (q == NULL) {
G.VNode[a].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
p = (ArcNode*)malloc(sizeof(ArcNode)); //再创建一个表示对称边的结点p
p->nextarc = NULL;
p->adjvex = a;
q = G.VNode[i].firstarc;
if (q == NULL) {
G.VNode[i].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
}
}
}
void Search_BFS(Graph G, int n) //以n为起点，BFS寻找特殊路径
{
queueQ;
Visit[n] = 1; //将起始点标记为已被访问过的状态
Q.push(n); //起始点入队
int m, t = 0;
while (!Q.empty()) {
m = Q.front(); //队头元素出队
Q.pop();
ArcNode* p = G.VNode[m].firstarc;
while (p) {
//遍历当前队头结点的所有邻接点，若邻接点已被访问过，则p继续向后遍历
//否则入队，并标记为已访问状态，防止重复入队
if (!Visit[p->adjvex] && p->adjvex >= n) {
if (p->adjvex >= G.VNode[m].maxdata) {
//如果新结点的值大于当前路径上的大值
cout<< n<< "-"<< p->adjvex<< " ";
sum++;
t = 1;
}
else {
G.VNode[p->adjvex].maxdata = G.VNode[m].maxdata;
}
Visit[p->adjvex] = 1;
Q.push(p->adjvex);
}
p = p->nextarc;
}
}
if (t) {
cout<< endl;
}
}
void Find(Graph G) //寻找特殊路径
{
for (int i = 1; i< G.vexnum; i++){
for (int i = 1; i<= G.vexnum; i++){
Visit[i] = 0; //辅助数组Visit初始化
G.VNode[i].maxdata = i; //当前结点所在路径上的大值初始化
}
Search_BFS(G, i);
}
}
运行结果：
7
0 5 5 1 4 1 4
1-4 1-6 1-5 1-7
2-5 2-7
3-5 3-7
4-5 4-7
特殊路径总数:10
这道题涉及到了树和图，以图为主。主要考查了图的建立和图的遍历。这里，我使用了邻接表作为基本数据结构，采用了BFS的遍历方法（关于邻接表和BFS在我之前的文章里讲过，这里就不再多说了）。总体上的时间复杂度约为O(n^2)。
以上是我对这道题的看法，很高兴能与大家分享。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站栏目：特殊路径统计（C++）-创新互联
标题网址：http://bjjierui.cn/article/jiieh.html
