吝啬的国度_链表

太过爱你忘了你带给我的痛 2022-07-12 12:12 147阅读 0赞

package 搜索;  
  
  
import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.Scanner;  
  
  
public class 吝啬的国度\_链表 \{  
static class Edge \{  
public int next;  
public Edge e;  
\}  
  
  
static int result\[\];  
static boolean visited\[\];  
static int m;  
static int s;  
static ArrayList<Edge> arr;  
  
  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner(System.in);  
int n = sc.nextInt();  
while (n-- > 0) \{  
m = sc.nextInt();  
s = sc.nextInt();  
arr = new ArrayList<Edge>();  
visited = new boolean\[m + 1\];  
result = new int\[m + 1\];  
for (int i = 0; i <= m; i++) \{  
arr.add(null);  
\}  
int i, a, b;  
Edge edge;  
for (i = 0; i < m - 1; i++) \{  
a = sc.nextInt();  
b = sc.nextInt();  
  
  
edge = new Edge();  
edge.next = b;  
edge.e = arr.get(a);  
arr.set(a, edge);  
  
  
edge = new Edge();  
edge.next = a;  
edge.e = arr.get(b);  
arr.set(b, edge);  
\}  
  
  
visited\[s\] = true;  
dfs(s);  
bfs();  
result\[s\] = -1;  
for (i = 1; i <= m; i++) \{  
System.out.print(result\[i\] + " ");  
\}  
\}  
\}  
  
  
private static void bfs() \{  
Queue<Integer> que = new LinkedList<Integer>();  
que.add(s);  
while (!que.isEmpty()) \{  
Integer poll = que.poll();  
Edge edge = arr.get(poll);  
while (edge != null) \{  
int next = edge.next;  
if (!visited\[next\]) \{  
visited\[next\] = true;  
result\[next\] = poll;  
que.add(next);  
\}  
edge = edge.e;  
\}  
\}  
  
  
\}  
  
  
private static void dfs(int s) \{  
Edge edge = arr.get(s);  
while (edge != null) \{  
int next = edge.next;  
if (!visited\[next\]) \{  
visited\[next\] = true;  
dfs(next);  
\}  
result\[next\] = s;  
edge = edge.e;  
\}  
  
  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关常见的链表——单向链表&双向链表&循环链表

目录目标结构图单向链表的数据结构示意图双向链表的数据结构示意图循环单向链表的数据结构示意图代码实现单向链表双向链表单向循环链表附加题

た入场券/ 2022年09月14日 09:49/ 0 赞/ 323 阅读

相关 nyoj 20 吝啬国度【dfs】

吝啬的国度时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路

男娘i/ 2022年08月18日 01:00/ 0 赞/ 119 阅读

相关 NYOJ-20 吝啬的国度

吝啬的国度时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连

末蓝、/ 2022年08月14日 04:56/ 0 赞/ 125 阅读

相关吝啬的国度

吝啬的国度时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城

﹏ヽ暗。殇╰゛Y/ 2022年08月07日 13:36/ 0 赞/ 124 阅读

相关吝啬的国度

吝啬的国度时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城

╰+攻爆jí腚メ/ 2022年07月12日 12:29/ 0 赞/ 141 阅读

相关吝啬的国度_链表_数组存储

package 搜索; import java.util.LinkedList; import java.util.Queue; import java

布满荆棘的人生/ 2022年07月12日 12:12/ 0 赞/ 139 阅读

相关吝啬的国度_链表

package 搜索; import java.util.ArrayList; import java.util.Arrays; import java

太过爱你忘了你带给我的痛/ 2022年07月12日 12:12/ 0 赞/ 148 阅读

相关吝啬的国度_链式前向星

package 搜索; import java.util.Arrays; import java.util.LinkedList; import java.util

一时失言乱红尘/ 2022年07月12日 12:12/ 0 赞/ 168 阅读

相关吝啬的国度_数组存储

package 搜索; import java.util.Scanner; /\ \ 采用数组存储，类似深搜。效率优 \/ public class 吝啬的

阳光穿透心脏的1/2处/ 2022年07月12日 12:12/ 0 赞/ 137 阅读

相关吝啬的国度

描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的

落日映苍穹つ/ 2022年06月15日 04:22/ 0 赞/ 143 阅读