# UVa 10959

Jump to navigation
Jump to 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 , a is optimal in terms of - the input can be - and that is all that is necessary for this problem, though we can do better if we consider the complexity in terms of and - the edges and vertices. We can get the running time to 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