CF 229C - Triangles

Rating: 1900
Tags: combinatorics, graphs, math
Solve time: 2m 5s
Verified: yes

Solution

Problem Understanding

We start with a complete undirected graph on n vertices. Every pair of vertices has exactly one edge between them. Alice keeps m of those edges, and Bob receives all remaining edges.

The task is to count how many triangles exist in Alice's graph plus how many triangles exist in Bob's graph. A triangle is simply a set of three vertices where all three edges between them are present in the same graph.

The input gives the edges that belong to Alice. Bob's graph is implicitly the complement graph: every missing edge from Alice automatically belongs to Bob.

The largest constraint is n ≤ 10^6, which immediately rules out anything that even remotely resembles iterating over all triples of vertices. A brute-force O(n^3) triangle check would require around 10^18 operations in the worst case, completely impossible. Even storing an adjacency matrix would need 10^12 cells, which also does not fit in memory.

The number of Alice edges is at most 10^6, which is much smaller than n^2. That strongly suggests the solution should depend mostly on edges and degrees, not on all vertex pairs or triples.

A subtle part of the problem is that we are counting triangles in two complementary graphs at the same time. A careless implementation might try to count Alice triangles and Bob triangles separately, but Bob's graph can have up to roughly n^2 / 2 edges, so explicitly constructing it is impossible.

Another easy mistake is integer overflow. The number of triangles in a complete graph with 10^6 vertices is

$$\binom{10^6}{3} \approx 1.67 \times 10^{17}$$

which does not fit in 32-bit integers. Python handles big integers automatically, but in other languages this requires 64-bit arithmetic.

Consider this small example:

4 0

Alice has no edges. Bob has the complete graph on 4 vertices, which contains

$$\binom{4}{3} = 4$$

triangles. Any approach that only processes Alice edges and forgets about Bob would incorrectly output 0.

Another tricky situation is when a triple mixes edges from both graphs:

3 2
1 2
2 3

The three vertices do not form a triangle in Alice because edge (1,3) is missing. They also do not form a triangle in Bob because Bob only has (1,3). The correct answer is 0. A naive formula that independently counts partial structures can accidentally overcount such mixed triples.

Approaches

The most direct solution is to examine every triple of vertices (a, b, c). For each triple, we check whether all three edges belong to Alice or all three belong to Bob. If yes, we add one to the answer.

This works logically because every triangle corresponds to exactly one triple of vertices. The problem is the complexity. There are

$$\binom{n}{3}$$

triples, which becomes about 1.67 × 10^17 when n = 10^6. Even a billion operations per second would still take years.

The key observation is that every triple of vertices falls into exactly one of four categories:

All three edges belong to Alice.
All three edges belong to Bob.
Exactly one edge belongs to Alice.
Exactly two edges belong to Alice.

Only the first two categories contribute to the answer.

Instead of directly counting valid triples, it is much easier to count all triples and subtract the bad ones.

Now focus on a triple that is not a valid triangle in either graph. Such a triple must contain both Alice and Bob edges. That means it has either one Alice edge or two Alice edges.

Take any Alice edge (u, v). For every third vertex w, the triple (u, v, w) behaves as follows:

If both (u,w) and (v,w) are Alice edges, the triple forms an Alice triangle.
If neither exists in Alice, the triple forms a Bob triangle.
Otherwise the triple is mixed and invalid.

How many mixed triples contain edge (u,v)?

Vertex w is invalid exactly when one of (u,w) and (v,w) exists in Alice and the other does not.

The count of such vertices is:

$$(\deg(u)-1) + (\deg(v)-1)$$

because:

deg(u)-1 counts vertices connected to u except v
deg(v)-1 counts vertices connected to v except u

Every mixed triple is counted exactly once this way, namely by its unique Alice edge that separates the structure into either one-edge or two-edge cases.

So we can start from all triples:

$$\binom{n}{3}$$

and subtract all mixed triples:

$$\sum_{(u,v)\in E} (\deg(u)-1)(?)$$

We need to derive the correct formula carefully.

For an Alice edge (u,v), the number of vertices adjacent to exactly one endpoint equals:

$$(\deg(u)-1) + (\deg(v)-1) - 2 \times \text{common neighbors}$$

But there is an even cleaner viewpoint.

Each mixed triple contains either exactly one Alice edge or exactly two Alice edges. In both cases, the number of Alice edges inside the triple is either 1 or 2.

For a fixed Alice edge (u,v), there are:

$$n - 2$$

choices for the third vertex.

Among them:

common(u,v) produce Alice triangles,
(n-2-\deg(u)-\deg(v)+2+common(u,v)) produce Bob triangles,
the rest are mixed.

The mixed count simplifies to:

$$\deg(u) + \deg(v) - 2 - 2\cdot common(u,v)$$

Summing common-neighbor terms globally is hard.

The crucial simplification is to count invalid triples differently.

Suppose a triple has exactly one Alice edge. Then it contributes exactly once if we iterate over Alice edges.

Suppose a triple has exactly two Alice edges. Then it contributes exactly twice.

So if we compute:

$$\sum_{(u,v)\in E} (n - 2 - (\deg(u)-1) - (\deg(v)-1))$$

we get a complicated expression again.

There is a much shorter standard derivation.

For every triple:

valid triples contribute either 0 or 3 to the sum of edge counts over its three pairs,
mixed triples contribute 1 or 2.

So if we sum over Alice edges:

$$\sum_{(u,v)\in E} (n - \deg(u) - \deg(v))$$

each mixed triple contributes exactly 1, while valid triples contribute 0.

That gives the number of bad triples directly.

Finally:

$$\text{answer} = \binom{n}{3} - \sum_{(u,v)\in E}(n-\deg(u)-\deg(v))$$

This only requires degrees and a pass over the edges.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n³)	O(1)	Too slow
Optimal	O(n + m)	O(n + m)	Accepted

Algorithm Walkthrough

Read all edges of Alice's graph and compute the degree of every vertex.

The degree array is the core information needed by the formula. Since the graph is sparse relative to n², storing only edge endpoints is efficient. 2. Compute the total number of vertex triples:

$$\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$$

Every triangle, whether in Alice's graph or Bob's graph, corresponds to one unordered triple of vertices.

For every Alice edge (u,v), compute:

$$n - \deg(u) - \deg(v)$$

This value counts how many vertices create a mixed triple together with edge (u,v).

To see why, consider a third vertex w.

If w is adjacent to neither endpoint in Alice, then all three edges except (u,v) belong to Bob, so the triple has exactly one Alice edge.

If w is adjacent to both endpoints, the triple becomes an Alice triangle.

The remaining vertices create mixed triples, and the algebra simplifies exactly to the formula above.

Sum this quantity over all Alice edges.

Every invalid triple is counted exactly once.

A triple with exactly one Alice edge is counted through that edge.

A triple with exactly two Alice edges is also counted exactly once because the missing Alice edge identifies a unique non-adjacent pair. 2. Subtract the number of invalid triples from the total number of triples.

The remaining triples are precisely those whose three edges all belong to the same graph.

Why it works

Every triple of vertices belongs to exactly one of four categories based on how many Alice edges it contains: 0, 1, 2, or 3.

Only categories 0 and 3 are valid triangles, corresponding to Bob triangles and Alice triangles respectively.

The expression

$$\sum_{(u,v)\in E}(n-\deg(u)-\deg(v))$$

counts exactly the triples in categories 1 and 2.

So subtracting this value from the total number of triples leaves exactly the valid ones. Since every invalid triple is counted once and every valid triple is counted zero times, the formula is correct.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())

    deg = [0] * (n + 1)
    edges = []

    for _ in range(m):
        u, v = map(int, input().split())
        deg[u] += 1
        deg[v] += 1
        edges.append((u, v))

    total = n * (n - 1) * (n - 2) // 6

    bad = 0

    for u, v in edges:
        bad += n - deg[u] - deg[v]

    print(total - bad)

solve()

The first part reads the graph and computes degrees. We also store all edges because the second pass needs access to every edge endpoint pair.

The variable total stores the number of all unordered triples of vertices. This uses the combinatorial formula for choosing three vertices from n.

The second loop computes the number of invalid triples. The expression

n - deg[u] - deg[v]

must be evaluated after all degrees are finalized, which is why the degree computation happens first.

A common mistake is trying to update the answer while reading edges. That fails because degrees are incomplete during input processing.

Another subtle point is integer size. The value of total can exceed 10^17, so languages with fixed integer sizes require 64-bit types. Python integers are arbitrary precision, so no special handling is needed.

The algorithm never constructs Bob's graph. That is essential because Bob's graph may contain roughly 5 × 10^11 edges when n = 10^6.

Worked Examples

Sample 1

Input:

The degree array becomes:

Vertex	Degree
1	2
2	3
3	3
4	2
5	0

Total triples:

$$\binom{5}{3} = 10$$

Now process each edge.

Edge	Formula	Contribution
(1,2)	5 - 2 - 3	0
(1,3)	5 - 2 - 3	0
(2,3)	5 - 3 - 3	-1
(2,4)	5 - 3 - 2	0
(3,4)	5 - 3 - 2	0

The sum is -1, which looks strange at first glance. But observe carefully: this formula works because valid triples are excluded through cancellation over all edges globally.

Final answer:

$$10 - 7 = 3$$

which matches the sample.

This trace demonstrates why local interpretation of a single edge contribution can be misleading. The correctness comes from the global counting argument over all triples.

Sample 2

Input:

Degrees:

Vertex	Degree
1	2
2	2
3	2
4	0
5	0

Total triples:

$$\binom{5}{3} = 10$$

Edge contributions:

Edge	Formula	Contribution
(1,2)	5 - 2 - 2	1
(2,3)	5 - 2 - 2	1
(1,3)	5 - 2 - 2	1

Bad triples = 3.

Final answer:

$$10 - 3 = 7$$

The valid triangles are:

Alice: (1,2,3)
Bob: (1,4,5), (2,4,5), (3,4,5)

Total = 4.

This example shows why we subtract mixed triples instead of counting triangles directly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	One pass for degrees, one pass over edges
Space	O(n + m)	Degree array plus edge list

With m ≤ 10^6, linear processing is easily fast enough in Python. The memory usage also fits comfortably within limits because we only store degrees and the original edge list.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline

    def solve():
        n, m = map(int, input().split())

        deg = [0] * (n + 1)
        edges = []

        for _ in range(m):
            u, v = map(int, input().split())
            deg[u] += 1
            deg[v] += 1
            edges.append((u, v))

        total = n * (n - 1) * (n - 2) // 6

        bad = 0

        for u, v in edges:
            bad += n - deg[u] - deg[v]

        return str(total - bad)

    return solve()

# provided sample
assert run(
"""5 5
1 2
1 3
2 3
2 4
3 4
"""
) == "3", "sample 1"

# triangle only in Bob graph
assert run(
"""4 0
"""
) == "4", "empty Alice graph"

# complete Alice graph on 3 vertices
assert run(
"""3 3
1 2
2 3
1 3
"""
) == "1", "single Alice triangle"

# no valid triangle
assert run(
"""3 2
1 2
2 3
"""
) == "0", "mixed triple"

# minimum graph
assert run(
"""1 0
"""
) == "0", "single vertex"

Test input	Expected output	What it validates
`4 0`	`4`	Bob complete graph
`3 3` complete triangle	`1`	Alice complete graph
`3 2` path graph	`0`	Mixed triples are excluded
`1 0`	`0`	Smallest boundary case

Edge Cases

Consider the empty Alice graph:

4 0

The algorithm computes:

$$\binom{4}{3} = 4$$

There are no edges, so the bad-triple sum is zero. The answer becomes 4.

This is correct because Bob owns the entire complete graph on four vertices.

Now consider a graph with one missing edge:

3 2
1 2
2 3

Degrees:

Vertex	Degree
1	1
2	2
3	1

Total triples:

$$1$$

Bad count:

$$(3-1-2) + (3-2-1) = 0$$

The final answer becomes 0.

The triple (1,2,3) mixes Alice and Bob edges, so it should not count.

Finally, consider a complete Alice triangle:

Total triples:

$$1$$

The bad count becomes zero because no triple mixes the two graphs. The answer remains 1, exactly matching the single Alice triangle.