# Introduction to Graphs

Authors: Darren Yao, Benjamin Qi

Contributors: Nathan Gong, Ryan Chou, Kevin Sheng, Nikhil Chatterjee

What graphs are.

Note: Graphs will become a key topic in higher divisions. For Bronze, graphs are just a nice way to think about the structure of our data.

Graphs can be used to represent many things, from images to wireless signals, but one of the simplest analogies is to a map. Consider a map with several cities and bidirectional roads connecting the cities. Some problems relating to graphs are:

Is city $A$ connected to city $B$? Consider a region to be a group of cities such that each city in the group can reach any other city in said group, but no other cities. How many regions are in this map, and which cities are in which region? (Silver)

What's the shortest distance I have to travel to get from city $A$ to city $B$? (Gold)

For now, it suffices to learn how graphs are represented (usually **adjacency
lists**).

Resources | ||||
---|---|---|---|---|

CSA | interactive | |||

CSA | interactive - adjacency lists and matrices | |||

CPH | graph terminology, representation | |||

IUSACO | graph basics and representation, trees | |||

PAPS | adjacency matrices, lists, maps |

## What Does a Bronze Graph Problem Look Like?

All of the problems below fall into at least one of the following two categories:

- The graph's structure is special (it's a tree, path, or a cycle).
- To solve the problem, all you need to do is iterate over the adjacency list of every vertex.

Knowing DFS can be helpful but it should not be required.

## Example - Livestock Lineup

Focus Problem – try your best to solve this problem before continuing!

View Internal SolutionThis problem has multiple solutions can you find one that runs in only $\mathcal{O}(n)$ time?

Hint 1

Solution with Graphs

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Silver | Normal | ## Show TagsColoring, Tree | |||

Bronze | Hard | ## Show TagsColoring | |||

Bronze | Hard | ## Show TagsDFS, Tree | |||

Bronze | Hard | ## Show TagsCycle, Permutation | |||

Bronze | Very Hard | ## Show TagsDFS, Tree | |||

Bronze | Very Hard | ## Show TagsTree |

## Check Your Understanding

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!