Link
题目大意应该是给雇主关系结构图， 是direct graph， 会给adjacent list， 好像允许有employee有>=1 boss。 一般首先会问这个关系是不是valid ？
我个人的理解valid是两个条件:
1. 所有的node都在一个群， 有一个root。
2. 不能有cycle。
因为题目允许有>=1 个boss， 所以indgree可以>=1。
我思路是两部：
1.所以node一个群， 把图当成indirect graph，然后union find， 看最后是不是所有都connected。
2.有向图 check cycle。
如果两步都通过，就说明是valid。
1. 地里最近常出现的雇主关系题 最开始就是dfs找有多少个员工 followup就是讨论一下各种可能出现的情况包括loop怎么判断
检查是树还是森林，使用dfs在无向graph上即可。
有无cycle，蠡口，儿凝器canFinish()最简单的是topological sort。
DFS无向图， 从任何一点出发， 走一边能全部visit并且不会遇到visited的node，就是tree吗？
不过这个题目，结构可能不是标准的tree， 因为可能允许一个node有多个parent。 这样用DFS可能不行。
恩， topological sorting查有向图cycle也可以。
orginization employee architecture, find eid score from repporting tree, find loops and dual reporting in reporting tree. 应该属于简单题，就是层次多 。
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 | package EmploySystem;
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<Character, List<Character>> map = new HashMap<>();
map.put('A', new ArrayList<>());
map.put('B', new ArrayList<>());
map.put('C', new ArrayList<>());
map.put('D', new ArrayList<>());
map.put('E', new ArrayList<>());
map.get('A').add('B');
map.get('A').add('C');
map.get('A').add('E');
map.get('B').add('A');
map.get('D').add('E');
boolean valid = isValid(map);
System.out.println("Valid: " + valid);
if(valid){
Set<Character> employees = getAllEmployees('A', map);
System.out.println(employees.toString());
}
}
static boolean hasCycle(Map<Character, List<Character>> map,
Set<Character> visited,
Set<Character> path,
char employee){
visited.add(employee);
if(map.containsKey(employee)){
for(char next : map.get(employee)){
if(path.contains(next)) return true;
if(!visited.contains(next)){
path.add(next);
if(hasCycle(map, visited, path, next)) return true;
path.remove(next);
}
}
}
return false;
}
static boolean isValid(Map<Character, List<Character>> map){
Set<Character> visited = new HashSet<>();
Set<Character> path = new HashSet<>();
for(char employee : map.keySet()){
path.add(employee);
if(hasCycle(map, visited, path, employee)) return false;
path.remove(employee);
}
return true;
}
static Set<Character> getAllEmployees(char employer,
Map<Character, List<Character>> map){
Set<Character> employees = new HashSet<>();
if(map.containsKey(employer)){
for(char employee : map.get(employer)){
employees.add(employee);
employees.addAll(getAllEmployees(employee, map));
}
}
return employees;
}
}
|
