[SOLUTION] Reach Anywhere SOLUTION CODECHEF

Problem SOLUTION CODECHEF

You are given a simple undirected graph with $N$ vertices and $M$ edges.

Find the smallest non-negative integer $K$ such that for every vertex $u$ ( $1 \leq u \leq N$ ), there exists a walk of length exactly $K$ from $1$ to $u$ .

If no such integer exists, print $- 1$ instead.

Notes:

It is allowed to repeat both vertices and edges in a walk.
The length of a walk equals the number of edges in it.

Input Format

The first line of input will contain a single integer $T$ , denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers $N$ and $M$ — the number of vertices and edges of the graph, respectively.
- The next $M$ lines describe the edges. The $i$ -th of these $M$ lines contains two space-separated integers $u_{i}$ and $v_{i}$ , denoting an edge between $u_{i}$ and $v_{i}$ .

Output Format

For each test case, output on a new line the answer: the minimum value of $K$ such that there exists a length- $K$ walk from $1$ to every other vertex; or $- 1$ if no such $K$ exists.

Constraints

$1 \leq T \leq 1 0^{3}$
$1 \leq N \leq 1 0^{5}$
$1 \leq M \leq min (2 N \cdot ( N - 1 ), 1 0^{5})$
$1 \leq u_{i}, v_{i} \leq N$
$u_{i} \neq = v_{i}$ for each $1 \leq i \leq M$ .
Each unordered pair $(u, v)$ appears at most once.
The sum of $N$ across all test cases doesn’t exceed $1 0^{5}$ .
The sum of $M$ across all test cases doesn’t exceed $1 0^{5}$ .

Sample 1:

Input

Output

2
-1

Explanation:

Test case $1$ : We have the following length- $2$ walks reaching every vertex:

$1 \to 2 \to 3$ to reach $3$ .
$1 \to 3 \to 2$ to reach $2$ .
$1 \to 2 \to 1$ to reach $1$ .
Note that we reuse an edge here, which is allowed.

Test case $2$ : It can be proved that no integer $K$ satisfying the condition exists.

SOLUTION

def find_minimum_K(N, M, edges):
def dfs(u, k):
visited[u] = True
min_K[u] = k
for v in graph[u]:
if not visited[v]:
dfs(v, max(k, min_K[u] + 1))

graph = [[] for _ in range(N)]
min_K = [float(‘inf’)] * N

for u, v in edges:
graph[u – 1].append(v – 1)
graph[v – 1].append(u – 1)

visited = [False] * N
dfs(0, 0)

if all(visited):
return max(min_K)
else:
return -1

# Input
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
result = find_minimum_K(N, M, edges)
print(result)