資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 演算法找到三個結點的連線數最多的元組
本教程將討論一個用來找到三個結點的連線數最多的元組的程式。
為此，我們將獲得一棵包含 N 個結點的樹。我們的任務是找到這樣三個結點，使連線它們的路勁中覆蓋的結點數最多。
示例
#include <bits/stdc++.h>
#define ll long long int
#define MAX 100005
using namespace std;
vector<int> nearNode[MAX];
bool isTraversed[MAX];
//storing the required nodes
int maxi = -1, N;
int parent[MAX];
bool vis[MAX];
int startnode, endnode, midNode;
//implementing DFS to search nodes
void performDFS(int u, int count) {
isTraversed[u] = true;
int temp = 0;
for (int i = 0; i < nearNode[u].size(); i++) {
if (!isTraversed[nearNode[u][i]]) {
temp++;
performDFS(nearNode[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
startnode = u;
}
}
}
void performDFS2(int u, int count) {
isTraversed[u] = true;
int temp = 0;
for (int i = 0; i < nearNode[u].size(); i++) {
if (!isTraversed[nearNode[u][i]] && !vis[nearNode[u][i]]) {
temp++;
performDFS2(nearNode[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
midNode = u;
}
}
}
//finding endnote of diameter
void performDFS1(int u, int count) {
isTraversed[u] = true;
int temp = 0;
for (int i = 0; i < nearNode[u].size(); i++) {
if (!isTraversed[nearNode[u][i]]) {
temp++;
parent[nearNode[u][i]] = u;
performDFS1(nearNode[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
endnode = u;
}
}
}
void calcTreeVertices() {
performDFS(1, 0);
for (int i = 0; i <= N; i++)
isTraversed[i] = false;
maxi = -1;
performDFS1(startnode, 0);
for (int i = 0; i <= N; i++)
isTraversed[i] = false;
int x = endnode;
vis[startnode] = true;
while (x != startnode) {
vis[x] = true;
x = parent[x];
}
maxi = -1;
for (int i = 1; i <= N; i++) {
if (vis[i])
performDFS2(i, 0);
}
}
int main() {
N = 4;
nearNode[1].push_back(6);
nearNode[2].push_back(0);
nearNode[1].push_back(7);
nearNode[3].push_back(0);
nearNode[1].push_back(2);
nearNode[4].push_back(0);
calcTreeVertices();
cout << "Nodes: (" << startnode << ", " << endnode << ", " << midNode << ")";
return 0;
}輸出
Nodes: (0, 0, 0)
更新於：2020 年 8 月 19 日
64 次瀏覽
廣告