APIO 2018 - Duathlon

Author: Andi Qu

TL;DR

Split the graph into its biconnected components. Then use complementary counting and subtract the number of bad triples from the total.

Intuition

Instead of finding the number of good triples, find the number of bad triples and subtract that from the number of all triples. This is called complementary counting and is useful in many counting problems.

What makes a bad triple? A triple (S,C,F)(S, C, F) is bad if the paths from SS to CC and CC to FF both pass through some bottleneck.

This suggests that our solution will involve articulation points. Since this problem is about reachability, we'll probably use biconnected components as well.

Splitting into BCCs

Imagine we have a second graph where:

  • Each biconnected component is also a node.
  • Each node in the original graph has an edge going to all biconnected components it's a part of.
  • There are no other edges.

Notice how this graph is a tree - if there is a cycle, then the biconnected components that are part of that cycle form a larger biconnected component by definition.

Counting the Bad Triples

Consider some articulation point PP that is part of some BCC BB.

If we remove PP from the graph, we are left with the smaller tree containing BB and several other smaller trees.

If SS and FF are both in the same smaller tree that doesn't contain BB, then CC can't be in the smaller tree containing BB.

The sum of such pairs (S,F)(S, F) is thus the number of bad triples each pair (B,P)(B, P) contributes to the total number of bad triples.

We can do a DFS to count these pairs.

Complexity

Time: O(N+M)\mathcal{O}(N + M).

Memory: O(N+M)\mathcal{O}(N + M).

Implementation

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
ll n, m, N, ans, sz[200001];
vector<int> graph[100001], bcc_graph[200001], stck;
int low[100001], tin[100001], timer = 1, bccs = 1;
void dfs(int node, int parent = 0) {

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!