UVa 10959

From Algorithmist
Jump to: navigation, search

10959 - The Party, Part I[edit]

Summary[edit]

Given an unweighted undirected graph, we're asked the find the distance from a single node (Don Giovanni) to everyone else. This is a simple Single Source Shortest Path (Shortest Path) problem.

Explanation[edit]

Since N\leq 1000, a O(N^{2}) is optimal in terms of N - the input can be O(N^{2}) - and that is all that is necessary for this problem, though we can do better if we consider the complexity in terms of V and E - the edges and vertices. We can get the running time to O(E+V) using simply breadth-first search.

Notes[edit]

This problem is just another disguise for the traditional Erdös numbers.

Input[edit]

2

5 6
0 1
0 2
3 2
2 4
4 3
1 2

5 6
0 1
0 2
3 2
2 4
4 3
1 2

Output[edit]

1
1
2
2

1
1
2
2