-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathProjectAnalysis.java
More file actions
106 lines (94 loc) · 4.23 KB
/
Copy pathProjectAnalysis.java
File metadata and controls
106 lines (94 loc) · 4.23 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
96
97
98
99
100
101
102
103
104
105
106
package leetcode.linkTable;
import java.util.*;
import java.util.stream.Collectors;
public class ProjectAnalysis {
static class Transition {
int uniqueId;
int projectNumber;
String in, out;
Transition(int uniqueId, int projectNumber, String in, String out) {
this.uniqueId = uniqueId;
this.projectNumber = projectNumber;
this.in = in;
this.out = out;
}
}
public static void main(String[] args) {
List<Transition> data = Arrays.asList(
new Transition(1, 1, "A", "B"), new Transition(2, 2, "H", "I"),
new Transition(3, 1, "C", "D"), new Transition(4, 1, "B", "C"),
new Transition(5, 2, "G", "H"), new Transition(6, 3, "M", "N"),
new Transition(7, 4, "Y", "Z"), new Transition(8, 3, "N", "O"),
new Transition(9, 4, "X", "Y"), new Transition(10, 1, "E", "F"),
new Transition(11, 5, "S", "T"), new Transition(12, 5, "T", "U"),
new Transition(13, 5, "U", "S"), new Transition(14, 6, "V", "W"),
new Transition(15, 6, "W", "W1"), new Transition(16, 6, "W1", "W2"),
new Transition(17, 6, "W2", "W")
);
Map<Integer, List<Transition>> projects = new TreeMap<>();
for (Transition t : data) {
projects.computeIfAbsent(t.projectNumber, k -> new ArrayList<>()).add(t);
}
// Sorting transitions within each project by unique ID
for (List<Transition> list : projects.values()) {
list.sort(Comparator.comparingInt(t -> t.uniqueId));
}
// Analyzing each project and printing the result
for (Map.Entry<Integer, List<Transition>> entry : projects.entrySet()) {
int projectNumber = entry.getKey();
List<Transition> transitions = entry.getValue();
System.out.println("项目" + projectNumber + ": " + analyzeProject(transitions));
}
}
private static String analyzeProject(List<Transition> transitions) {
Map<String, String> map = new HashMap<>();
Set<String> allNodes = new HashSet<>();
for (Transition t : transitions) {
map.put(t.in, t.out);
allNodes.add(t.in);
allNodes.add(t.out);
}
Set<String> visited = new HashSet<>();
List<String> chains = new ArrayList<>();
boolean hasCycle = false;
Set<String> cycleNodes = new HashSet<>();
// Detect all chains and cycles
for (String node : allNodes) {
if (!visited.contains(node) && map.containsKey(node)) {
List<String> path = new ArrayList<>();
Set<String> pathNodes = new HashSet<>();
String current = node;
while (current != null && !pathNodes.contains(current)) {
pathNodes.add(current);
path.add(current);
current = map.get(current);
}
if (current != null && pathNodes.contains(current)) {
hasCycle = true; // A cycle is detected
int index = path.indexOf(current);
List<String> cycle = path.subList(index, path.size());
cycle.add(current);
chains.add("Cycle: " + String.join(" -> ", cycle));
cycleNodes.addAll(cycle);
} else {
chains.add("Chain: " + String.join(" -> ", path));
}
visited.addAll(pathNodes);
}
}
// Determine if it's a full cycle, partial cycle or just chains
if (hasCycle) {
if (cycleNodes.size() < allNodes.size()) {
return "中心成圈: " + chains.stream().filter(s -> s.startsWith("Cycle")).findFirst().orElse("");
} else {
return "成圈: " + chains.stream().filter(s -> s.startsWith("Cycle")).findFirst().orElse("");
}
} else {
if (chains.size() > 1) {
return "成链但不全,存在多条链: " + chains.stream().filter(s -> s.startsWith("Chain")).collect(Collectors.joining(", "));
} else {
return "成链: " + chains.get(0);
}
}
}
}