G家店面

海拔2纳米 发表于 2018-5-6 10:23
是的，不是n*n没法in place，是个大水题

谢谢楼主～

第二题感觉一个hashmap就搞定了。关键是在做set_manager, set_peer时看有没有环出现

第二题：

1. public class QueryMangerImpl implements QueryManger{
   
2. 
   
3.     Map<Integer, Integer> employmentMap;
   
4. 
   
5.     public QueryMangerImpl () {}
   
6. 
   
7.     @Override
   
8.     public void setManger(int manager, int employee) throws CyclicRelationFoundException {
   
9.         if (queryManager(employee, manager)) {
   
10.             throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s",
    
11.                     manager, employee));
    
12.         }
    
13.         employmentMap.put(employee, manager);
    
14.     }
    
15. 
    
16.     @Override
    
17.     public void setPeer(int managerFrom, int employee) throws EmployeeNotFoundException, CyclicRelationFoundException {
    
18.         if (!employmentMap.containsKey(managerFrom)) {
    
19.             throw new EmployeeNotFoundException(String.format("Employee %s is not found"));
    
20.         }
    
21.         int newManager = employmentMap.get(managerFrom);
    
22.         if (queryManager(employee, newManager)) {
    
23.             throw new CyclicRelationFoundException(String.format("There is management relation from %s to %s", newManager, employee));
    
24.         }
    
25.         employmentMap.put(employee, newManager);
    
26.     }
    
27. 
    
28.     @Override
    
29.     public boolean queryManager(int manager, int employee) {
    
30.         if (manager == employee) {
    
31.             return false;
    
32.         }
    
33.         while (employmentMap.containsKey(employee)) {
    
34.             employee = employmentMap.get(employee);
    
35.             if (employee == manager) {
    
36.                 return true;
    
37.             }
    
38.         }
    
39.         return false;
    
40.     }
    
41. 
    
42. }
    
43. 
    
44. public interface QueryManger {
    
45.     public void setManger(int manager, int employee) throws CyclicRelationFoundException;
    
46.     public void setPeer(int managerFrom, int target) throws CyclicRelationFoundException, EmployeeNotFoundException;
    
47.     public boolean queryManager(int manager, int employee);
    
48. }
    
49. 
    
50. public class CyclicRelationFoundException extends Exception {
    
51.     public CyclicRelationFoundException(String message) {
    
52.         super(message);
    
53.     }
    
54. }
    

复制代码

1. public class EmployeeNotFoundException extends Exception {
   
2.     public EmployeeNotFoundException(String message) {
   
3.         super(message);
   
4.     }
   
5. }
   

复制代码

拓扑排序？

union find