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 as a node.

  • If two nodes and 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 nodes and edges, can you remove some edge to break the graph into 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.

Code

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first

Give Us Feedback on VT HSPC 2014 - Birthday Party!

Join the Discussion!

Feel free to voice your thoughts in the comments section.