//遍歷有向圖(鄰接表)中的每一個(gè)子圖并計(jì)算權(quán)值(子圖中的每一個(gè)結(jié)點(diǎn)權(quán)值相乘)
#include <iostream>
#include <string>
#include<vector>
using namespace std;
#define MAXVEX 100
typedef int VertexType; //頂點(diǎn)類型
typedef int EdgeType; //邊上的權(quán)值類型
struct EdgeNode //邊表結(jié)點(diǎn)
{
int adjvex; //鄰接點(diǎn)域骨饿,存儲(chǔ)該節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)
EdgeType weight; //存儲(chǔ)權(quán)值衣迷,非網(wǎng)圖不需要
EdgeNode* next; //下一個(gè)鄰接點(diǎn)
};
typedef struct VertexNode
{
VertexType data; //頂點(diǎn)
EdgeNode* firstEdge; //邊表頭指針
}AdjList[MAXVEX]; //頂點(diǎn)數(shù)組
struct GraphAdjList
{
AdjList adjList; //頂點(diǎn)數(shù)組
int numVertexes, numEdges; //實(shí)際圖中頂點(diǎn)數(shù)和邊數(shù)
};
bool* visited;
static vector<int> weight;
int w = 1;
void DFS(GraphAdjList G, int v)
{
w *= G.adjList[v].data;
//cout << G.adjList[v].data << " "; //輸出頂點(diǎn)名稱
visited[v] = true;
EdgeNode* p = G.adjList[v].firstEdge; //頂點(diǎn)的第一條邊
while (p)
{
if (!visited[p->adjvex])
{
DFS(G, p->adjvex);
}
p = p->next;
}
}
//根據(jù)頂點(diǎn)名稱查找其下標(biāo)
int locateVertex(GraphAdjList G, VertexType v)
{
for (int i = 0; i < G.numVertexes; i++)
{
if (v == G.adjList[i].data)
{
return i;
}
}
return -1;
}
static void yinzi()
{
int count = 0;
for (int i = 0; i < weight.size(); i++)
{
for (int j = 1; j * j <= weight[i]; j++)
{
if (weight[i] % j == 0)
{
count++;
if (j != weight[i] / j)
{
count++;
}
}
}
}
cout << count << endl;
}
int main()
{
//建立有向圖的鄰接矩陣
GraphAdjList G;
cin >> G.numVertexes;
G.numEdges = G.numVertexes - 1;
visited = new bool[G.numVertexes];
for (int i = 0; i < G.numVertexes; i++)
{
visited[i] = false; //初始化為false
}
//輸入頂點(diǎn)
for (int i = 0; i < G.numVertexes; i++)
{
cin >> G.adjList[i].data;
G.adjList[i].firstEdge = NULL;
}
//輸入邊
VertexType vertex1, vertex2;
int m, n;
int edge = 1;
for (int i = 0; i < G.numEdges; i++)
{
cin >> vertex1 >> vertex2; //輸入邊及其依附的兩個(gè)頂點(diǎn)
m = locateVertex(G, vertex1); //弧的起點(diǎn)
n = locateVertex(G, vertex2); //弧的終點(diǎn)
if (m >= 0 && n >= 0)
{
//創(chuàng)建一個(gè)新的邊結(jié)點(diǎn)
EdgeNode* e = new EdgeNode;
e->weight = edge;
e->adjvex = n;
e->next = G.adjList[m].firstEdge; //頭插法插入頂點(diǎn)的firstedge
G.adjList[m].firstEdge = e;
}
}
for (int i = 0; i < G.numVertexes; i++) //每個(gè)頂點(diǎn)遍歷一遍
{
w = 1;
if (!visited[i])
{
DFS(G, i);
}
weight.push_back(w);
//cout << endl;
for (int j = 0; j < G.numVertexes; j++)
{
visited[j] = false; //復(fù)位訪問標(biāo)志位false
}
}
yinzi();
return 0;
}