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 other's 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 \leq p \leq 100)$ nodes and $c \: (0 \leq c \leq 5000)$ edges, can you remove some edge to break the graph into more than one connected component?

Applying DFS

Since the constraints on edges (and nodes) is small, we can run DFS on the graph. 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 "YES". Otherwise, if we're able to visit every node for each edge that gets removed, the answer is "NO" (notice the problem asks whether it's impossible to invite everyone).

Ignoring Edges

The easiest way to ignore edges in a graph is to represent the graph with an adjacency matrix (we can do this because the number of nodes is very small). To ignore an edge that connects two nodes $a$ and $b$, we can simply set adj[a][b] and adj[b][a] to false. Later, when we want to add the edge back, we can update adj[a][b] and adj[b][a] to true.

Implementation

Copy
#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

Copy
import java.util.*;

public class BirthdayParty {
	static int p, c;
	static boolean[][] adj;
	static boolean[] vis;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);