PrevNext
Somewhat Frequent
 0/7

Introduction to Graphs

Authors: Darren Yao, Benjamin Qi

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

What graphs are.

Edit This Page

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:

  1. Is city AA connected to city BB? 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)

  2. What's the shortest distance I have to travel to get from city AA to city BB? (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 Solution

This problem has multiple solutions. Can you find one that runs in only O(n)\mathcal{O}(n) time?

Hint

Solution with Graphs - Livestock Lineup

While you can brute force all possible permutations of the cows, there is a solution that works in just O(N)\mathcal{O}(N), involving graphs!

Notice that since the input is guaranteed to be valid, we're always going to end up with "chains" of cows that we can arrange as we please. Using the sample given in the problem, we'd get a "chain" representation like this:

Chains

Note that cows that are not part of any chain can be considered their own chains of length 1 for implementation purposes.

With this representation in mind, we can iterate through the cows in lexicographical order. When we visit a cow that could be a possible start of a chain (a cow that only has one required neighbor), we go through its neighbors, adding cows as we go along, until we hit an end.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <algorithm>
#include <fstream>
#include <map>
#include <string>
#include <vector>
using std::endl;
using std::string;
using std::vector;

Java

import java.io.*;
import java.util.*;
public class LineUp {
// Assumed to be in sorted order (which it is)
static final String[] COWS = new String[] {
"Beatrice", "Belinda", "Bella", "Bessie", "Betsy", "Blue", "Buttercup", "Sue"};
public static void main(String[] args) throws IOException {
Map<String, Integer> cowInds = new HashMap<>();

Python

COWS = sorted(
["Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"]
)
cow_inds = {c: i for i, c in enumerate(COWS)}
neighbors = [[] for _ in range(len(COWS))]
with open("lineup.in") as read:
for _ in range(int(read.readline())):
words = read.readline().strip().split()

Problems

StatusSourceProblem NameDifficultyTags
SilverNormal
Show TagsColoring, Tree
BronzeHard
Show TagsColoring
BronzeHard
Show TagsDFS, Tree
BronzeHard
Show TagsCycle, Permutation
BronzeVery Hard
Show TagsDFS, Tree
BronzeVery Hard
Show TagsTree

Check Your Understanding

How many connected components are in the following graph? Graph

Question 1 of 6

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!

PrevNext