-
Notifications
You must be signed in to change notification settings - Fork 13
/
Graph_CheckIfUndirectedGraphIsConnected.java
112 lines (91 loc) · 3.62 KB
/
Graph_CheckIfUndirectedGraphIsConnected.java
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
107
108
109
110
111
112
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
// https://thecodingsimplified.com/check-if-undirected-graph-is-connected/
// https://www.geeksforgeeks.org/graph-and-its-representations/
// https://algorithms.tutorialhorizon.com/check-if-given-undirected-graph-is-connected-or-not/
public class Graph_CheckIfUndirectedGraphIsConnected {
private static boolean isGraphConnected(Graph graph) {
int startingNode = 0;
dfs(graph, startingNode);
for (int i = 0; i < graph.isVisited.length; i++) {
if(!graph.isVisited[i]) {
return false;
}
}
return true;
}
private static void dfs(Graph graph, int startingNode) {
boolean[] isVisited = graph.isVisited;
List<List<Integer>> adjList = graph.adjList;
//System.out.println("DFS from node " + startingNode);
dfsUtil(startingNode, isVisited, adjList);
//System.out.println();
}
private static void dfsUtil(int node, boolean[] isVisited, List<List<Integer>> adjList) {
isVisited[node] = true;
//System.out.print(node + " ");
for (Integer integer : adjList.get(node)) {
node = integer;
if (!isVisited[node]) {
dfsUtil(node, isVisited, adjList);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
while (t-->0) {
int nodes = Integer.parseInt(br.readLine().trim()); // nodes is 7
int edges = Integer.parseInt(br.readLine().trim());
Graph graph = new Graph(nodes);
/*for (int i = 0; i < edges; i++) {
String[] nodeAB = br.readLine().trim().split("\\s+");
int nodeA = Integer.parseInt(nodeAB[0]);
int nodeB = Integer.parseInt(nodeAB[1]);
graph.addEdges(nodeA, nodeB);
}*/
graph.addEdges(0, 1);
graph.addEdges(0, 2);
graph.addEdges(1, 3);
graph.addEdges(2, 4);
graph.addEdges(3, 5);
graph.addEdges(4, 5);
System.out.println(isGraphConnected(graph)); // now graph is not connected
//graph.addEdges(4, 6); //this edge will make the graph connected
//System.out.println(isGraphConnected(graph)); // now graph is connected
printGraph(graph);
//int startingNode = 0;
//dfs(graph, startingNode);
}
}
private static void printGraph(Graph graph) {
List<List<Integer>> adjList = graph.adjList;
for (int i = 0; i < adjList.size(); i++) {
System.out.print(i + " -> ");
for (int j = 0; j < adjList.get(i).size(); j++) {
System.out.print(adjList.get(i).get(j) + " ");
}
System.out.println();
}
}
static class Graph {
private int nodes;
private List<List<Integer>> adjList;
private boolean[] isVisited;
Graph(int nodes) {
this.nodes = nodes;
adjList = new ArrayList<>();
isVisited = new boolean[nodes];
for(int i = 0; i < nodes; i++) {
adjList.add(i, new ArrayList<>());
}
}
private void addEdges(int sourceNode, int destinationNode) {
adjList.get(sourceNode).add(destinationNode);
adjList.get(destinationNode).add(sourceNode);
}
}
}