#41. Clone graph
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. Moreover:
- acyclic graph
- root value is 1
- node values are unique starting from 1
/* class Node {
public int val;
public List
class Solution {
Map<Integer, Node> visited;
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
visited = new HashMap<>();
Node copy = cloneGraph(node, null);
visited.clear();
return copy;
}
private Node cloneGraph(Node node, Node from) {
Node copy = new Node(node.val);
visited.put(copy.val, copy);
List<Node> neighbors = new ArrayList<>();
if (from != null) {
neighbors.add(visited.get(from.val));
}
visitNeighbors(node, from, neighbors);
copy.neighbors = neighbors;
return copy;
}
private void visitNeighbors(Node original, Node from, List<Node> neighbors) {
for (Node neighbor : original.neighbors) {
if (from != null && neighbor.val == from.val) {
continue;
}
if (visited.containsKey(neighbor.val)) {
neighbors.add(visited.get(neighbor.val));
} else {
Node newNeigh = cloneGraph(neighbor, original);
neighbors.add(newNeigh);
}
}
}
}
#42. Course schedule (Aflarea dacă un graf orientat conține cicluri)
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array of prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
// solutie cu timp ridicat de executie
class Solution {
public boolean canFinish(int numCourses, int[][] prereq) {
if (prereq.length == 0) {
return true;
}
Map<Integer, List<Integer>> edges = new HashMap<>();
for (int i=0; i<numCourses; i++) {
edges.put(i, new ArrayList<>());
}
for (int i=0; i < prereq.length; i++) {
int from = prereq[i][0], to = prereq[i][1];
if (from == to) {
return false;
}
edges.get(from).add(to);
}
Set<Integer> visited = new HashSet<>();
for (int i=0; i<numCourses; i++) {
if (!visited.contains(i)) {
boolean res = dfs(i, edges, new HashSet<>(), visited);
if (!res) {
return false;
}
}
}
return true;
}
private boolean dfs(int node, Map<Integer, List<Integer>> edges, Set<Integer> ancestors, Set<Integer> visited) {
visited.add(node);
boolean res = true;
for (int neighbor : edges.get(node)) {
if (ancestors.contains(neighbor)) {
return false;
}
Set<Integer> copy = new HashSet<>(ancestors);
copy.add(node);
res = res && dfs (neighbor, edges, copy, visited);
}
return res;
}
}
// solutie acceptabila
class Solution {
public boolean canFinish(int numCourses, int[][] prereq) {
if (prereq.length == 0) {
return true;
}
// init
Map<Integer, Set<Integer>> edges = new HashMap<>();
for (int i=0; i<numCourses; i++) {
edges.put(i, new HashSet<>());
}
// build edges & do basic checks
for (int i=0; i < prereq.length; i++) {
int from = prereq[i][0], to = prereq[i][1];
if (from == to) {
return false;
}
if (edges.containsKey(to) && edges.get(to).contains(from)) {
return false;
}
edges.get(from).add(to);
}
// simplify, add/remove edges using transitions
// if 1->2 and 2->3 then 1->3
// if 3->1 then false
boolean doContinue = true;
while (doContinue) {
doContinue = false;
Iterator<Integer> aSet = edges.keySet().iterator();
while (aSet.hasNext()) {
int a = aSet.next();
Set<Integer> toAdd = new HashSet<>();
Set<Integer> toRemove = new HashSet<>();
Iterator<Integer> bSet = edges.get(a).iterator();
while (bSet.hasNext()) {
int b = bSet.next();
if (edges.containsKey(b)) {
Iterator<Integer> cSet = edges.get(b).iterator();
while (cSet.hasNext()) {
int c = cSet.next();
if (edges.containsKey(c) && edges.get(c).contains(a)) {
return false;
}
if (!edges.get(a).contains(c)) {
// edges.get(a).add(c); // ConcurrentModificationException
toAdd.add(c);
doContinue = true;
}
}
}
// edges.get(a).remove(b); // ConcurrentModificationException
toRemove.add(b);
}
edges.get(a).removeAll(toRemove);
edges.get(a).addAll(toAdd);
}
}
return true;
}
}
Niciun comentariu:
Trimiteți un comentariu