forked from damaohongtu/JavaInterview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMain_3.java
More file actions
95 lines (83 loc) · 2.61 KB
/
Main_3.java
File metadata and controls
95 lines (83 loc) · 2.61 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package BiShi.WeBank;
import java.io.File;
import java.util.*;
/**
* @Author MaoTian
* @Classname Main_3
* @Description TODO
* @Date 下午5:36 2019/9/19
* @Version 1.0
* @Created by mao<[email protected]>
*/
public class Main_3 {
//邻接表
public static HashMap<Integer,List<Integer>> v=new HashMap<>();
//保存路径
public static List<Integer> path=new ArrayList<>();
//所有可能的路径
public static List<List<Integer>> res=new ArrayList<>();
public static void dfs(int B,int E){
path.add(B);
if(B==E){
res.add(new ArrayList<>(path));
path.remove(path.size()-1);
return;//注意退出
}
for (int i = 0; i <v.get(B).size() ; i++) {
//避免重复访问
if(path.contains(v.get(B).get(i))){
continue;
}
// B--->i---->E,通过中间节点到end
dfs(v.get(B).get(i),E);
}
path.remove(path.size()-1);
}
public static void main(String[] args)throws Exception {
Scanner sc =new Scanner(new File("/home/mao/workspace/面试/JavaGuide/JavaInterview/java/src/BiShi/WeBank/main_3"));
//Scanner sc =new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
//记录所有的节点
List<Integer>node=new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
node.add(a);
node.add(b);
//无向图，添加ab和ba
if (v.containsKey(a)){
v.get(a).add(b);
}else {
List<Integer> tmp=new ArrayList<>();
tmp.add(b);
v.put(a,tmp);
}
if (v.containsKey(b)){
v.get(b).add(a);
}else {
List<Integer> tmp=new ArrayList<>();
tmp.add(a);
v.put(b,tmp);
}
}
int B = sc.nextInt();
int E = sc.nextInt();
dfs(B, E);
Set<Integer> set1=new HashSet<>();
set1.addAll(node);
Set<Integer> set2=new HashSet<>();
for (List<Integer> l:res){
for(Integer i:l){
set2.add(i);
}
}
for (Integer i:set1){
if(!set2.contains(i)){
System.out.print(i+" ");
}
}
}
}
}