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

布满荆棘的人生 2022-07-12 12:12 140阅读 0赞

package 搜索;  
  
  
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 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 Edge\[m + 1\];  
visited = new boolean\[m + 1\];  
result = new int\[m + 1\];  
for (int i = 0; i <= m; i++) \{  
arr\[i\] = 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\[a\];  
arr\[a\] = edge;  
  
  
edge = new Edge();  
edge.next = a;  
edge.e = arr\[b\];  
arr\[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\[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\[s\];  
while (edge != null) \{  
int next = edge.next;  
if (!visited\[next\]) \{  
visited\[next\] = true;  
dfs(next);  
\}  
result\[next\] = s;  
edge = edge.e;  
\}  
  
  
\}  
\}

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 125 阅读

相关吝啬的国度

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

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

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

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

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

相关吝啬的国度_链表

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

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

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

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

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

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

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

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

相关吝啬的国度

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

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

相关图的存储方式（数组+链表的存储方式）

![70][] ![70 1][] [70]: /images/20220413/93f57fcb217442ce9b35fa7181e0555a.png [70 1]:

不念不忘少年蓝@/ 2022年04月13日 07:53/ 0 赞/ 203 阅读