Created
June 9, 2023 10:49
-
-
Save akashks1998/53c978ddbdac8bca1dd9a81c291c5b91 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package com.isolatedCity; | |
| import java.util.ArrayList; | |
| import java.util.HashMap; | |
| import java.util.List; | |
| import java.util.Map; | |
| public class IsolatedCity { | |
| private static void dfs(int u, List<List<Pair>> adjList, List<Pair> edges, List<Node> nodes, int color) { | |
| if (nodes.get(u).getVisited()) { | |
| return; | |
| } | |
| nodes.get(u).setVisited(true); | |
| nodes.get(u).setColor(color); | |
| for (Pair v : adjList.get(u)) { | |
| if (nodes.get(v.getU()).getVisited()) { | |
| continue; | |
| } | |
| edges.get(v.getV()).setUsed(true); | |
| nodes.get(v.getU()).setParent(u); | |
| nodes.get(v.getU()).setParentEdge(v.getV()); | |
| edges.get(v.getV()).setDirection(v.getU() == edges.get(v.getV()).getV()); | |
| dfs(v.getU(), adjList, edges, nodes, color); | |
| } | |
| } | |
| public static void printIsolatedCities(Integer n, List<Pair> edges) { | |
| List<List<Pair>> adjList = new ArrayList<>(); | |
| for (int i = 0; i < n; i++) { | |
| adjList.add(new ArrayList<>()); | |
| } | |
| for (int i = 0; i < edges.size(); i++) { | |
| Pair edge = edges.get(i); | |
| adjList.get(edge.getU()).add(new Pair(edge.getV(), i)); | |
| adjList.get(edge.getV()).add(new Pair(edge.getU(), i)); | |
| } | |
| List<Node> nodes = new ArrayList<>(); | |
| for (int i = 0; i < n; i++) { | |
| Node node = new Node(); | |
| node.setId(i); | |
| nodes.add(node); | |
| } | |
| int color = 0; | |
| List<Boolean> containsIsolated = new ArrayList<>(); | |
| for (int i = 0; i < n; i++) { | |
| if (nodes.get(i).getVisited()) { | |
| continue; | |
| } | |
| containsIsolated.add(true); | |
| dfs(i, adjList, edges, nodes, color); | |
| color++; | |
| } | |
| for (Pair pair : edges) { | |
| if (!pair.isUsed() && containsIsolated.get(nodes.get(pair.getU()).getColor())) { | |
| pair.setDirection(false); | |
| Node currentNode = nodes.get(pair.getU()); | |
| Node initialNode = currentNode; | |
| containsIsolated.set(currentNode.getColor(), false); | |
| while (currentNode.getParent() != -1) { | |
| Node parentNode = nodes.get(currentNode.getParent()); | |
| Pair parentEdge = edges.get(currentNode.getParentEdge()); | |
| parentEdge.setDirection(!parentEdge.isDirection()); | |
| parentNode.setParent(currentNode.getId()); | |
| currentNode = parentNode; | |
| } | |
| initialNode.setParent(-1); | |
| initialNode.setParentEdge(-1); | |
| } | |
| } | |
| int sm = 0; | |
| for (Boolean aBoolean : containsIsolated) { | |
| if (aBoolean) { | |
| sm++; | |
| } | |
| } | |
| System.out.println("Total Isolated Nodes: " + sm); | |
| for (Pair edge : edges) { | |
| if (edge.isDirection()) { | |
| System.out.println(edge.getU() + "->" + edge.getV()); | |
| } else { | |
| System.out.println(edge.getV() + "->" + edge.getU()); | |
| } | |
| } | |
| } | |
| public static void main(String[] args) { | |
| List<Pair> edges = new ArrayList<>(); | |
| edges.add(new Pair(1, 2)); | |
| edges.add(new Pair(1, 3)); | |
| edges.add(new Pair(1, 4)); | |
| edges.add(new Pair(1, 5)); | |
| edges.add(new Pair(2, 5)); | |
| edges.add(new Pair(4, 6)); | |
| edges.add(new Pair(6, 9)); | |
| edges.add(new Pair(4, 9)); | |
| edges.add(new Pair(7, 8)); | |
| printIsolatedCities(10, edges); | |
| } | |
| public static class Pair { | |
| private int u; | |
| private int v; | |
| private boolean used; | |
| private boolean direction; | |
| public Pair(int u, int v) { | |
| this.u = u; | |
| this.v = v; | |
| } | |
| public int getU() { | |
| return u; | |
| } | |
| public void setU(int u) { | |
| this.u = u; | |
| } | |
| public int getV() { | |
| return v; | |
| } | |
| public void setV(int v) { | |
| this.v = v; | |
| } | |
| public boolean isUsed() { | |
| return used; | |
| } | |
| public void setUsed(boolean used) { | |
| this.used = used; | |
| } | |
| public boolean isDirection() { | |
| return direction; | |
| } | |
| public void setDirection(boolean direction) { | |
| this.direction = direction; | |
| } | |
| } | |
| public static class Node { | |
| private Integer id; | |
| private Integer parent = -1; | |
| private Boolean visited = false; | |
| private Integer parentEdge=-1; | |
| private Integer color; | |
| public Integer getParentEdge() { | |
| return parentEdge; | |
| } | |
| public void setParentEdge(Integer parentEdge) { | |
| this.parentEdge = parentEdge; | |
| } | |
| public Integer getId() { | |
| return id; | |
| } | |
| public void setId(Integer id) { | |
| this.id = id; | |
| } | |
| public Integer getParent() { | |
| return parent; | |
| } | |
| public void setParent(Integer parent) { | |
| this.parent = parent; | |
| } | |
| public Boolean getVisited() { | |
| return visited; | |
| } | |
| public void setVisited(Boolean visited) { | |
| this.visited = visited; | |
| } | |
| public Integer getColor() { | |
| return color; | |
| } | |
| public void setColor(Integer color) { | |
| this.color = color; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The problem that was occuring was on line 58, I set
pair.setDirection(true);instead of false