Articulation Points
Wed Nov 06 2024 18:45:39 GMT+0000 (Coordinated Universal Time)
Saved by @signup_returns
//Articulation Points
import java.util.*;
public class ArticulationPoints {
private int numVertices;
private int[][] adjacencyMatrix;
private int[] discoveryTime;
private int[] lowLinkValue;
private int timeCounter;
private Set<Integer> articulationPoints;
public ArticulationPoints(int numVertices) {
this.numVertices = numVertices;
adjacencyMatrix = new int[numVertices][numVertices];
discoveryTime = new int[numVertices];
lowLinkValue = new int[numVertices];
timeCounter = 1;
articulationPoints = new HashSet<>();
}
public void readGraph(Scanner scanner) {
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
adjacencyMatrix[i][j] = scanner.nextInt();
}
discoveryTime[i] = 0;
}
}
public void findArticulationPoints(int currentVertex, int parentVertex) {
discoveryTime[currentVertex] = timeCounter;
lowLinkValue[currentVertex] = timeCounter;
timeCounter++;
int childrenCount = 0;
for (int adjacentVertex = 0; adjacentVertex < numVertices; adjacentVertex++) {
if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && discoveryTime[adjacentVertex] == 0) {
if (parentVertex == -1) childrenCount++;
findArticulationPoints(adjacentVertex, currentVertex);
if (parentVertex != -1 && lowLinkValue[adjacentVertex] >= discoveryTime[currentVertex]) {
articulationPoints.add(currentVertex);
}
lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], lowLinkValue[adjacentVertex]);
} else if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && adjacentVertex != parentVertex) {
lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], discoveryTime[adjacentVertex]);
}
}
if (parentVertex == -1 && childrenCount > 1) {
articulationPoints.add(currentVertex);
}
}
public void printResults() {
System.out.println("Articulation points: " + articulationPoints);
System.out.print("Discovery times: ");
for (int i = 0; i < numVertices; i++) {
System.out.print(discoveryTime[i] - 1 + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter number of vertices:");
int numVertices = scanner.nextInt();
ArticulationPoints articulation = new ArticulationPoints(numVertices);
System.out.println("Enter the adjacency matrix:");
articulation.readGraph(scanner);
articulation.findArticulationPoints(0, -1);
articulation.printResults();
}
}
// Input for Test Case with 4 vertices
/*
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
*/
// Expected Output
/*
Articulation points: [1, 2]
Discovery times: 0 1 2 3
*/



Comments