本文共 4092 字，大约阅读时间需要 13 分钟。
一 、 DFS
#include#include #include #define MAX 20005using namespace std;int m, n;vector g[MAX];int max_i = 0;int max_s = 0;int visit[MAX] = {0};void dfs(int cur, int s) { if(s > max_s){ max_s = s; max_i = cur; } for(int i = 0; i < g[cur].size(); i++ ){ int v = g[cur][i]; if(visit[v] == 0){ visit[v] = 1; dfs(v, s+1); visit[v] = 0; } } return ; } int main() { cin >> m >> n; int x; for(int i = 2; i <= m+n; i++ ){ cin >> x; g[i].push_back(x); //区别与 普通数组的 矩阵 这里 模拟邻接表 g[x].push_back(i); } visit[1] = 1; dfs(1, 0); int temp = max_i; max_i = 0; max_s = 0; memset(visit, 0, sizeof(visit));//很重要 不要忘记 dfs(temp, 0); cout << max_s; return 0; }
二 、 BFS
#includeJava DFS#include #include #include #define MAX 20005using namespace std;int m, n;vector g[MAX];queue que;int max_i = 0;int max_s = 0;int dist[MAX] = {0}; //记录 int visit[MAX] = {0};void bfs(int cur) { que.push(cur); while(!que.empty()){ int v = que.front(); que.pop();//记得 及时 出队 for(int i = 0; i < g[v].size(); i++ ){ int xx = g[v][i]; if(visit[xx] == 0){ que.push(xx); dist[xx] = dist[v] + 1; visit[xx] = 1; } } } } int main() { cin >> m >> n; int x; for(int i = 2; i <= m+n; i++ ){ cin >> x; g[i].push_back(x); g[x].push_back(i); } visit[1] = 1; bfs(1); for(int i = 1; i <= m+n; i++ ){ if(dist[i] > max_s){ max_i = i; max_s = dist[i]; } } memset(visit, 0, sizeof(visit));//很重要 memset(dist, 0, sizeof(dist));//都要 置为0 bfs(max_i); for(int i = 1; i <= m+n; i++ ){ if(dist[i] > max_s){ max_i = i; max_s = dist[i]; } } cout << max_s; return 0; }
import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;import java.util.List;import java.util.Scanner;public class Main { List []list; boolean []visit; int max_i; int max_s; public static void main(String[] args) { new Main().run(); } public void run() { Scanner in = new Scanner(System.in); int n, m; n = in.nextInt(); m = in.nextInt(); list = new LinkedList[m+n+1];//创建时候不能带具体类型 visit = new boolean[m+n+1]; Arrays.fill(visit, false); for(int i = 0; i < list.length; i++ ) { list[i] = new LinkedList<>(); } int x; for(int i = 2; i <= m+n; i++ ) { x = in.nextInt(); list[i].add(x); list[x].add(i); } visit[1] = true; dfs(1, 0); int temp = max_i; Arrays.fill(visit, false); dfs(temp, 0); System.out.println(max_s); } public void dfs(int cur, int s) { if(s > max_s) { max_i = cur; max_s = s; } for(int i = 0; i < list[cur].size(); i++ ) { int v = list[cur].get(i); if(!visit[v]) { visit[v] = true; dfs(v, s+1); } } }}
Java BFS
import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main { LinkedList []list; boolean []visit; int dist[]; int max_s; int max_i; public static void main(String[] args) { new Main().run(); } public void run() { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); list = new LinkedList[m+n+1]; visit = new boolean[m+n+1]; dist = new int[m+n+1]; Arrays.fill(visit, false); for(int i = 0; i < list.length; i++ ) { list[i] = new LinkedList<>(); } int x; for(int i = 2; i <= m+n; i++ ) { x = in.nextInt(); list[i].offer(x); list[x].offer(i); } Arrays.fill(dist, 0); max_i = 1; max_s = 0; visit[1] = true; bfs(1); for(int i = 1; i < dist.length; i++ ) { if(dist[i] > max_s) { max_s = dist[i]; max_i = i; } } Arrays.fill(dist, 0); Arrays.fill(visit, false); bfs(max_i); max_s = 0; for(int i = 1; i < dist.length; i++ ) { if(dist[i] > max_s) { max_s = dist[i]; } } System.out.println(max_s); } public void bfs(int cur) { Queue que = new LinkedList<>(); que.offer(cur); visit[cur] = true; while(!que.isEmpty()) { int v = que.poll(); for(int i = 0; i < list[v].size(); i++ ) { int t = list[v].get(i); if(!visit[t]) { visit[t] = true; que.offer(t); dist[t] = dist[v] + 1; } } } } }
转载地址：http://eoimi.baihongyu.com/