VT HSPC 2014 - Birthday Party

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

• If two nodes $a$ and $b$ 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(1\le p\le 100)$ nodes and $c(0\le c\le 5000)$ edges, can you remove some edge to break the graph into $\ge 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.

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