試統(tǒng)計樹上一共有多少條特殊路徑。
[輸入格式]
+ 第一行包含一個整數(shù)N，代表節(jié)點數(shù)
+ 第二行包含N個整數(shù)p1，p2，…，pn，代表每個節(jié)點的父節(jié)點編號。若pi=0，則該節(jié)點為樹的根節(jié)點
[輸出數(shù)據(jù)]
輸出樹上一共有多少條特殊路徑
[補充說明]
+ 0≤pi≤N
+ 有且僅有一個pi=0
+ 輸入的圖是一棵樹
[樣例1]
輸入：
7
0 5 5 1 4 1 4
輸出：
10
[樣例2]
輸入：
5
2 3 0 2 2
輸出：
7
其中樣例1的圖形示例：
分析：
首先，它是一棵樹，這個條件可以保證圖中任意兩點之間都是連通的。然后，我們要把它作為一個無向連通圖來處理。這里，我們以鄰接表為基本的數(shù)據(jù)結(jié)構(gòu)。要找到所有特殊路徑，從本質(zhì)上看，就是讓我們對圖進行遍歷。我們以從點1出發(fā)為例，每遍歷到一個點，只有當這個點比路徑上的初始點大時，我們才把它加入路徑，另外，把它與這條路徑上的大值作比較，若新增的點較大，則表示一條新的特殊路徑的產(chǎn)生，輸出這條路徑上的首尾點，并更新這條路上的大點。這樣，我們依次從1開始遍歷（1是起始點），就可以找到所有特殊路徑。關(guān)于如何保存大點的問題，可以給結(jié)構(gòu)體增加一個變量，保存當前結(jié)點所在路徑上的大值。
程序代碼：?
# include# include# define SIZE 20
# define NEWSIZE 20
using namespace std;
//以鄰接表為基本數(shù)據(jù)結(jié)構(gòu)
typedef struct ArcNode { //邊的結(jié)點結(jié)構(gòu)類型
int adjvex; //該邊的終點編號
struct ArcNode* nextarc; //指向下一條邊的指針
}ArcNode;
typedef struct VexNode { //頂點結(jié)構(gòu)
int data; //當前結(jié)點的值
int maxdata; //當前結(jié)點所在路徑上的大值
ArcNode* firstarc; //指向第一條與該頂點有關(guān)的邊的指針
}VexNode;
typedef struct Graph { //鄰接表結(jié)構(gòu)類型
VexNode* VNode; //定義鄰接表
int vexnum; //頂點個數(shù)
int size; //鄰接表的大小
}Graph;
int sum = 0; //特殊路徑總數(shù)
int* Visit; //輔助數(shù)組，標記點是否已被訪問過
void Create(Graph& G); //創(chuàng)建
void Find(Graph G); //尋找全部特殊路徑
int main()
{
Graph G;
Create(G); //創(chuàng)建
cout<< endl;
Find(G); //尋找全部特殊路徑
cout<< "特殊路徑總數(shù):"<< sum<< endl;
return 0;
}
void Create(Graph& G) //創(chuàng)建
{
cin >>G.vexnum; //輸入頂點個數(shù)
G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
G.size = SIZE;
while (G.size< G.vexnum) {
//根據(jù)點的個數(shù)動態(tài)分配空間
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)); //創(chuàng)建一個用于存放當前邊的結(jié)點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)); //再創(chuàng)建一個表示對稱邊的結(jié)點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; //將起始點標記為已被訪問過的狀態(tài)
Q.push(n); //起始點入隊
int m, t = 0;
while (!Q.empty()) {
m = Q.front(); //隊頭元素出隊
Q.pop();
ArcNode* p = G.VNode[m].firstarc;
while (p) {
//遍歷當前隊頭結(jié)點的所有鄰接點，若鄰接點已被訪問過，則p繼續(xù)向后遍歷
//否則入隊，并標記為已訪問狀態(tài)，防止重復(fù)入隊
if (!Visit[p->adjvex] && p->adjvex >= n) {
if (p->adjvex >= G.VNode[m].maxdata) {
//如果新結(jié)點的值大于當前路徑上的大值
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; //輔助數(shù)組Visit初始化
G.VNode[i].maxdata = i; //當前結(jié)點所在路徑上的大值初始化
}
Search_BFS(G, i);
}
}
運行結(jié)果：?
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
特殊路徑總數(shù):10
這道題涉及到了樹和圖，以圖為主。主要考查了圖的建立和圖的遍歷。這里，我使用了鄰接表作為基本數(shù)據(jù)結(jié)構(gòu)，采用了BFS的遍歷方法（關(guān)于鄰接表和BFS在我之前的文章里講過，這里就不再多說了）?？傮w上的時間復(fù)雜度約為O(n^2)。
以上是我對這道題的看法，很高興能與大家分享。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
網(wǎng)站題目：特殊路徑統(tǒng)計（C++）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來于：http://weahome.cn/article/jiieh.html
重慶分公司
重慶分公司
