VT HSPC 2014 - Birthday Party

Author: Michael Cao

In this problem, we're given some people who have others numbers, and are asked whether if some pair of friends lose each others numbers it will be impossible to invite everyone.

Generating the Graph

Once we've dissected the text in the problem statement, we can apply the following definitions:

  • Define a person xx as a node.

  • If two nodes aa and bb have each others numbers, connect them with an undirected edge.

  • Everyone can be invited to the party if there exists exactly one connected component in the graph.

Now the problem becomes: given a graph with p(1p100)p (1 \leq p \leq 100) nodes and c(0c5000)c (0 \leq c \leq 5000) edges, can you remove some edge to break the graph into 1\geq 1 connected component?

Applying DFS

Since the constraints on edges (and nodes) is small, we can apply dfs. For each edge, let's run a DFS while ensuring we don't traverse that edge. If we can't visit some node, then the answer is "NO". Otherwise, if we can visit every node after trying to remove every edge, the answer is "YES". Check the code for more information on how to ignore an edge while DFS-ing.

Implementation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

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!