Day 28 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/diameter-of-a-graph/1

Graph Diameter

Difficulty: Medium Accuracy: 77.95%

You are given an undirected connected graph with V vertices numbered from 0 to V-1 and E edges, represented as a 2D array edges[][], where each element edges[i] = [u, v] represents an undirected edge between vertex u and vertex v.
Find the diameter of the graph.
The diameter of a graph (sometimes called the width) is the number of edges on the longest path between two vertices in the graph.
Note: Graph do not contains any cycle.

Examples :
Input: V = 6, E = 5, edges[][] = [[0, 1], [0, 4], [1, 3], [1, 2], [2, 5]]

Output: 4
Explanation: The longest path in the graph is from vertices 4 to vertices 5 (4 -> 0 -> 1 -> 2 -> 5).

Input: V = 7, E = 6, edges[][] = [[0, 2], [0, 4], [0, 3], [3, 1], [3, 5], [1, 6]]

Output: 4
Explanation: The longest path in the graph is from vertices 2 to vertices 6 (2 -> 0 -> 3 -> 1 -> 6).

Constraints:
2 ≤ V ≤ 105
1 ≤ E ≤ V - 1
0 ≤ edges[i][0], edges[i][1] < V

Solution:
from collections import deque

class Solution:
def diameter(self, V, edges):
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)

    def bfs(start):
        q = deque([(start, 0)])
        visited = set([start])
        farthest_node, max_dist = start, 0
        while q:
            node, dist = q.popleft()
            if dist > max_dist:
                max_dist, farthest_node = dist, node
            for nei in adj[node]:
                if nei not in visited:
                    visited.add(nei)
                    q.append((nei, dist + 1))
        return farthest_node, max_dist

    node1, _ = bfs(0)
    _, diameter = bfs(node1)
    return diameter