Hey everyone! In this article, we've compiled a list of essential graph algorithms that are a must-learn for anyone interested in graph theory. Whether you're a student, preparing for an upcoming interview, this cheatsheet serves as a handy reference for quick revision and mastery. So, let's dive in and explore the key graph algorithms you need to know!
Topics Covered
- BFS
- DFS
- Topological sort
- Dijkstra algorithm
- SCC(stongly connected components)
- MST(minimum spanning tree)
- Bellman ford algorithm
- Floyd warshall algorithm
- Eulerian path
BFS
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order, meaning it visits all the vertices at the same level before moving on to the next level.
Starting from a given vertex, BFS traverses the graph by visiting all the vertices in the same level, and then moves to the next level. It uses a queue data structure to maintain the order of traversal, and a visited array to keep track of the visited vertices.
BFS can be used to solve various graph problems, such as finding the shortest path between two vertices, detecting cycles in a graph, and checking whether a graph is bipartite.
import java.util.*;
public class BFS {
private int vertices; // number of vertices
private List<Integer>[] adjList; // adjacency list
private boolean[] visited; // to keep track of visited vertices
public BFS(int vertices) {
this.vertices = vertices;
adjList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<>();
}
visited = new boolean[vertices];
}
public void addEdge(int u, int v) {
adjList[u].add(v);
}
public void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
public static void main(String[] args) {
BFS bfs = new BFS(6);
bfs.addEdge(0, 1);
bfs.addEdge(0, 2);
bfs.addEdge(1, 2);
bfs.addEdge(1, 3);
bfs.addEdge(2, 3);
bfs.addEdge(2, 4);
bfs.addEdge(3, 4);
bfs.addEdge(3, 5);
bfs.addEdge(4, 5);
bfs.bfs(0); // start BFS from vertex 0
}
}DFS
DFS stands for Depth First Search. It is a graph traversal algorithm that explores as far as possible along each branch before backtracking. In other words, it starts at a root vertex and explores as far as possible along each branch before backtracking. During the traversal, it keeps track of visited nodes to ensure that it doesn't revisit a node that has already been visited.
DFS can be used to solve a variety of problems such as finding connected components, detecting cycles in a graph, and generating mazes. It can also be used to perform topological sorting, which is the process of arranging nodes in a directed acyclic graph in such a way that every node comes before all the nodes that depend on it.
DFS can be implemented recursively or iteratively using a stack data structure
import java.util.*;
public class DFS {
private int vertices; // number of vertices
private List<Integer>[] adjList; // adjacency list
private boolean[] visited; // to keep track of visited vertices
public DFS(int vertices) {
this.vertices = vertices;
adjList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<>();
}
visited = new boolean[vertices];
}
public void addEdge(int u, int v) {
adjList[u].add(v);
}
public void dfs(int start) {
visited[start] = true;
System.out.print(start + " ");
for (int neighbor : adjList[start]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
public static void main(String[] args) {
DFS dfs = new DFS(6);
dfs.addEdge(0, 1);
dfs.addEdge(0, 2);
dfs.addEdge(1, 2);
dfs.addEdge(1, 3);
dfs.addEdge(2, 3);
dfs.addEdge(2, 4);
dfs.addEdge(3, 4);
dfs.addEdge(3, 5);
dfs.addEdge(4, 5);
dfs.dfs(0); // start DFS from vertex 0
}
}Topological Sort
Topological sorting is the process of arranging the nodes in a directed acyclic graph (DAG) in such a way that every node comes before all the nodes that depend on it. In other words, it is a linear ordering of vertices that satisfies the following condition: if there is an edge from vertex u to vertex v, then u comes before v in the ordering.
Topological sorting is commonly used in job scheduling, task sequencing, and dependency resolution. For example, suppose you have a list of tasks that depend on each other, and you want to execute them in the correct order. You can use topological sorting to determine the correct order of execution.
Topological sorting can be performed using DFS or BFS. The DFS-based approach involves visiting the nodes in a depth-first manner and keeping track of the finish times of the nodes. The nodes are then sorted in decreasing order of finish time to get the topological ordering. The BFS-based approach involves using a queue and maintaining the in-degree of each node. The nodes are processed in a way that the node with zero in-degree is processed first and its adjacent nodes' in-degree is decremented.
Topological sorting is only applicable to directed acyclic graphs, which means that there should be no cycles in the graph. If the graph contains cycles, then topological sorting is not possible.
Topological sort using Kahn's algorithm
import java.util.*;
class Graph {
private int V; // number of vertices
private List<Integer>[] adj; // adjacency list
Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
// add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// perform topological sort using Kahn's algorithm
List<Integer> topologicalSortKahn() {
// calculate in-degrees of all vertices
int[] inDegree = new int[V];
for (int v = 0; v < V; v++) {
for (int w : adj[v]) {
inDegree[w]++;
}
}
// add all vertices with in-degree 0 to the queue
Queue<Integer> queue = new LinkedList<>();
for (int v = 0; v < V; v++) {
if (inDegree[v] == 0) {
queue.offer(v);
}
}
// perform topological sort
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int v = queue.poll();
result.add(v);
// decrement in-degree of all adjacent vertices
for (int w : adj[v]) {
inDegree[w]--;
if (inDegree[w] == 0) {
queue.offer(w);
}
}
}
// if the result size is less than V, there is a cycle in the graph
if (result.size() < V) {
throw new RuntimeException("Graph contains cycle");
}
return result;
}
}
public class Main {
public static void main(String[] args) {
// create a sample graph
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
// perform topological sort
System.out.print("Topological sort: ");
List<Integer> result = g.topologicalSortKahn();
for (int v : result) {
System.out.print(v + " ");
}
}
}Topological sort using DFS
import java.util.*;
class Graph {
private int V; // number of vertices
private List<Integer>[] adj; // adjacency list
Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
// add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// perform topological sort using DFS
List<Integer> topologicalSortDFS() {
boolean[] visited = new boolean[V];
boolean[] stack = new boolean[V];
Stack<Integer> result = new Stack<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (!dfs(i, visited, stack, result)) {
throw new RuntimeException("Graph contains cycle");
}
}
}
List<Integer> resultList = new ArrayList<>();
while (!result.isEmpty()) {
resultList.add(result.pop());
}
return resultList;
}
private boolean dfs(int v, boolean[] visited, boolean[] stack, Stack<Integer> result) {
visited[v] = true;
stack[v] = true;
for (int w : adj[v]) {
if (!visited[w]) {
if (!dfs(w, visited, stack, result)) {
return false;
}
} else if (stack[w]) {
return false;
}
}
stack[v] = false;
result.push(v);
return true;
}
}
public class Main {
public static void main(String[] args) {
// create a sample graph
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
// perform topological sort
System.out.print("Topological sort: ");
List<Integer> result = g.topologicalSortDFS();
for (int v : result) {
System.out.print(v + " ");
}
}
}Dijkstra algorithm
Dijkstra's algorithm is a shortest path algorithm used to find the shortest path between a source node and all other nodes in a weighted graph. The algorithm maintains a priority queue of nodes to visit and a set of visited nodes. It starts with the source node and visits its neighbors, updating their distances from the source node. It then selects the node with the smallest distance and repeats the process until all nodes are visited. The algorithm is guaranteed to find the shortest path in a graph with non-negative edge weights.
import java.util.*;
public class Graph {
private final int n; // Number of nodes
private final List<Integer>[] adjList;
public Graph(int n) {
this.n = n;
this.adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v) {
adjList[u].add(v);
adjList[v].add(u); // Assuming undirected graph
}
public void dijkstra(int source) {
boolean[] visited = new boolean[n];
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparing(Node::getDistance));
pq.offer(new Node(source, 0));
while (!pq.isEmpty()) {
Node currNode = pq.poll();
int curr = currNode.getNode();
if (visited[curr]) {
continue;
}
visited[curr] = true;
for (int neighbor : adjList[curr]) {
int next = neighbor;
int newDist = dist[curr] + 1; // Assuming edge weight is 1
if (!visited[next] && newDist < dist[next]) {
dist[next] = newDist;
pq.offer(new Node(next, newDist));
}
}
}
// Print the shortest distances from the source node to all other nodes
for (int i = 0; i < n; i++) {
System.out.println("Shortest distance from source to node " + i + " is " + dist[i]);
}
}
public static void main(String[] args) {
int n = 5; // Number of nodes in the graph
Graph graph = new Graph(n);
// Adding edges to the graph
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 3);
// Running Dijkstra's algorithm from the source node (node 0)
graph.dijkstra(0);
}
}
class Node {
private final int node;
private final int distance;
public Node(int node, int distance) {
this.node = node;
this.distance = distance;
}
public int getNode() {
return node;
}
public int getDistance() {
return distance;
}
}Strongly connected components in Graph
SCC (Strongly Connected Components) is a concept in graph theory that refers to a subset of vertices in a directed graph where every vertex is reachable from every other vertex in the same subset. In other words, SCC is a group of vertices that have a mutual path to reach each other.
The identification of SCCs in a graph is a fundamental problem in graph theory, with applications in many fields such as network analysis, compiler optimization, and database schema design.
The process of identifying SCCs typically involves running a graph traversal algorithm such as Tarjan's algorithm or Kosaraju's algorithm. These algorithms work by performing a DFS (depth-first search) on the graph, and keeping track of the strongly connected components as they are identified.
Once the SCCs have been identified, they can be used for various purposes. For example, in network analysis, SCCs can be used to identify clusters of closely connected nodes, while in compiler optimization, SCCs can be used to optimize code by identifying sections of code that can be rearranged or parallelized without changing the program's behavior.
Kosaraju's algorithm for finding strongly connected component (SCC)
import java.util.*;
public class Graph {
private final int n; // Number of nodes
private final List<Integer>[] adjList;
public Graph(int n) {
this.n = n;
this.adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v) {
adjList[u].add(v);
}
public List<List<Integer>> kosaraju() {
// Step 1: Perform DFS on the graph and store the nodes in the order of their finishing times
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, visited, stack);
}
}
// Step 2: Reverse the graph
Graph reversedGraph = getReversedGraph();
// Step 3: Perform DFS on the reversed graph in the order of the finishing times from Step 1
List<List<Integer>> stronglyConnectedComponents = new ArrayList<>();
Arrays.fill(visited, false);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
List<Integer> component = new ArrayList<>();
reversedGraph.dfs(node, visited, component);
stronglyConnectedComponents.add(component);
}
}
return stronglyConnectedComponents;
}
private void dfs(int node, boolean[] visited, List<Integer> component) {
visited[node] = true;
component.add(node);
for (int neighbor : adjList[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, component);
}
}
}
private Graph getReversedGraph() {
Graph reversedGraph = new Graph(n);
for (int i = 0; i < n; i++) {
for (int neighbor : adjList[i]) {
reversedGraph.addEdge(neighbor, i);
}
}
return reversedGraph;
}
public static void main(String[] args) {
int n = 8; // Number of nodes in the graph
Graph graph = new Graph(n);
// Adding edges to the graph
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 3);
graph.addEdge(2, 6);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(4, 0);
graph.addEdge(4, 5);
graph.addEdge(5, 6);
graph.addEdge(6, 5);
graph.addEdge(6, 7);
graph.addEdge(7, 7);
// Running Kosaraju's algorithm to find strongly connected components
List<List<Integer>> stronglyConnectedComponents = graph.kosaraju();
// Print the strongly connected components
System.out.println("Strongly connected components:");
for (List<Integer> component : stronglyConnectedComponents) {
System.out.println(component);
}
}
}Tarjan's algorithm to find strongly connect components
import java.util.*;
public class Graph {
private int V;
private List<Integer>[] adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int u, int v) {
adj[u].add(v);
}
public List<List<Integer>> tarjan() {
List<List<Integer>> result = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
int[] low = new int[V];
int[] ids = new int[V];
Arrays.fill(ids, -1);
int id = 0;
for (int i = 0; i < V; i++) {
if (ids[i] == -1) {
dfs(i, low, ids, stack, id, result);
}
}
return result;
}
private void dfs(int current, int[] low, int[] ids, Stack<Integer> stack, int id, List<List<Integer>> result) {
stack.push(current);
ids[current] = low[current] = id++;
for (int neighbor : adj[current]) {
if (ids[neighbor] == -1) {
dfs(neighbor, low, ids, stack, id, result);
low[current] = Math.min(low[current], low[neighbor]);
} else if (stack.contains(neighbor)) {
low[current] = Math.min(low[current], ids[neighbor]);
}
}
if (low[current] == ids[current]) {
List<Integer> component = new ArrayList<>();
int node;
do {
node = stack.pop();
component.add(node);
} while (node != current);
result.add(component);
}
}
}Minimum spanning tree
MST (Minimum Spanning Tree) is a fundamental concept in graph theory that refers to a subset of edges in an undirected graph that connects all vertices of the graph with the minimum possible total edge weight. In other words, it is the tree that spans all the vertices of a graph with the minimum sum of edge weights.
Prim's algorithm to find MST
import java.util.*;
public class Graph {
private int V;
private List<Edge>[] adjList;
public Graph(int V) {
this.V = V;
adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
}
public void addEdge(int u, int v, int weight) {
adjList[u].add(new Edge(v, weight));
adjList[v].add(new Edge(u, weight));
}
public List<Edge> primMST() {
boolean[] visited = new boolean[V];
int[] parent = new int[V];
int[] key = new int[V];
Arrays.fill(key, Integer.MAX_VALUE);
PriorityQueue<Edge> pq = new PriorityQueue<>(V, new Edge());
List<Edge> mst = new ArrayList<>();
key[0] = 0;
pq.offer(new Edge(0, 0));
while (!pq.isEmpty()) {
int u = pq.poll().v;
visited[u] = true;
for (Edge e : adjList[u]) {
int v = e.v;
int weight = e.weight;
if (!visited[v] && weight < key[v]) {
key[v] = weight;
parent[v] = u;
pq.offer(new Edge(v, key[v]));
}
}
}
for (int i = 1; i < V; i++) {
mst.add(new Edge(i, parent[i], key[i]));
}
return mst;
}
private static class Edge implements Comparator<Edge> {
int v;
int weight;
public Edge() {}
public Edge(int v, int weight) {
this.v = v;
this.weight = weight;
}
public Edge(int v, int u, int weight) {
this.v = v;
this.weight = weight;
}
@Override
public int compare(Edge e1, Edge e2) {
return e1.weight - e2.weight;
}
}
}Kruskal's algorithm to find MST
import java.util.*;
class Graph {
int V, E;
List<Edge> edges;
public Graph(int V, int E) {
this.V = V;
this.E = E;
this.edges = new ArrayList<>();
}
public void addEdge(int u, int v, int w) {
edges.add(new Edge(u, v, w));
}
public List<Edge> kruskalMST() {
List<Edge> result = new ArrayList<>();
// Sort edges by weight
Collections.sort(edges);
// Create disjoint set union (DSU) data structure
DSU dsu = new DSU(V);
for (Edge edge : edges) {
int u = edge.u;
int v = edge.v;
int w = edge.w;
int uParent = dsu.find(u);
int vParent = dsu.find(v);
// Check if adding this edge will form a cycle
if (uParent != vParent) {
result.add(edge);
dsu.union(uParent, vParent);
}
}
return result;
}
}
class Edge implements Comparable<Edge> {
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge other) {
return this.w - other.w;
}
}
class DSU {
int[] parent;
int[] rank;
public DSU(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
// Union by rank
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[xRoot] = yRoot;
rank[yRoot]++;
}
}
}Bellman ford algorithm
Bellman-Ford algorithm is a single-source shortest path algorithm that works for graphs with negative edge weights, but does not work for graphs with negative cycles. The algorithm initializes the distance to the source vertex as 0 and all other distances as infinity. It then relaxes all the edges in the graph repeatedly, for a total of V-1 times, where V is the number of vertices in the graph.
In each iteration, the algorithm relaxes all the edges, i.e., for each edge (u, v) in the graph, if the distance to the source vertex through u is smaller than the current distance to v, the algorithm updates the distance to v to be the distance to u plus the weight of the edge (u, v).
After V-1 iterations, the algorithm checks for negative cycles. If a negative cycle is found, the algorithm reports that the graph contains a negative cycle. Otherwise, the algorithm returns the shortest distance from the source vertex to all other vertices in the graph.
import java.util.*;
public class Graph {
private int V; // number of vertices
private List<Edge> edges; // list of edges
private List<Integer>[] adj; // adjacency list
public Graph(int V) {
this.V = V;
edges = new ArrayList<>();
adj = new List[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
// add edge to the graph
public void addEdge(int u, int v, int w) {
edges.add(new Edge(u, v, w));
adj[u].add(v);
}
// Bellman-Ford algorithm
public int[] bellmanFord(int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// relax all edges V-1 times
for (int i = 0; i < V-1; i++) {
for (Edge e : edges) {
int u = e.u;
int v = e.v;
int w = e.w;
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// check for negative cycles
for (Edge e : edges) {
int u = e.u;
int v = e.v;
int w = e.w;
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
System.out.println("Graph contains negative cycle");
return null;
}
}
return dist;
}
// inner class for representing edges
private class Edge {
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
}
}
Floyd-Warshall algorithm
Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices in a weighted graph. It works by iteratively considering all possible intermediate vertices between each pair of vertices, and updating the shortest path if a shorter path is found through the intermediate vertex. This algorithm can handle negative weight edges, but not negative weight cycles.
public class Graph {
private int V; // number of vertices
private List<Integer>[] adjList; // adjacency list
public Graph(int V) {
this.V = V;
adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
}
// method to add an edge to the graph
public void addEdge(int u, int v) {
adjList[u].add(v);
}
// method to compute all pairs shortest paths using Floyd-Warshall algorithm
public int[][] floydWarshall() {
int[][] dist = new int[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = Integer.MAX_VALUE;
}
}
}
// initialize distances based on the graph edges
for (int u = 0; u < V; u++) {
for (int v : adjList[u]) {
dist[u][v] = 1; // assuming unit weight edges
}
}
// compute shortest paths for all pairs of vertices
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
}Eulerian path
Eulerian path is a path in a graph that visits every edge exactly once. Hierholzer's algorithm is an efficient algorithm for finding an Eulerian path in a graph.
In Hierholzer's algorithm, we start with an arbitrary vertex and follow a trail of edges until we return to the starting vertex. If we have visited all edges, we have found an Eulerian circuit, otherwise we continue from an unvisited vertex and repeat the process until we have visited all edges.
import java.util.*;
public class Graph {
private int V;
private List<Integer>[] adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; i++) {
adj[i] = new ArrayList<Integer>();
}
}
public void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
public List<Integer> findEulerianPath() {
List<Integer> path = new ArrayList<Integer>();
if (!hasEulerianPath()) {
return path;
}
int start = 0;
for (int i = 0; i < V; i++) {
if (adj[i].size() % 2 != 0) {
start = i;
break;
}
}
ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
stack.push(start);
while (!stack.isEmpty()) {
int u = stack.peek();
if (adj[u].size() == 0) {
path.add(stack.pop());
} else {
int v = adj[u].get(0);
adj[u].remove(0);
adj[v].remove(Integer.valueOf(u));
stack.push(v);
}
}
return path;
}
public boolean hasEulerianPath() {
int odd = 0;
for (int i = 0; i < V; i++) {
if (adj[i].size() % 2 != 0) {
odd++;
}
}
if (odd > 2) {
return false;
}
return true;
}
}Happy Coding !!!