Hello, Codeforces community.

Today, I will be talking about a little known trick that allows you to search a graph with M^2 (or E^2) edges. This trick uses a set and BFS, and is named after the infamous USACO problem Pie for a Pie.

First off, I want to thank two orzosities who taught me this trick. Thank you, lunchbox and PurpleCrayon!

Prerequisites: - C++ Set / Graph Theory

Let's get into it.

First problem: 0-1 MST

Abridged problem statement:

You're given an undirected graph of n nodes with n(n-1)/2 total edges (it is complete). You are given m edges, where the length is 1, and the rest of the n(n-1)/2 — m edges are of length 0. Find the Minimum Spanning Tree (MST) of this graph.

Solution:

It can be shown that our MST will consist of as many edges of 0 that we can add (lets call a collection of nodes with the same length 0 connected to each other a connected component). Therefore, there will be a select number of 1s that we must use to connect these components. It turns out that the number of 1s we need to use is equivalent to the number of connected components in the graph subtracted by 1.

Now, our problem is reduced down to find the number of connected components with the length of 0. Naive DFS or BFS takes O(V + E) time, where V = n and E = n(n-1)/2. It can be shown then, that our current code would be in O(N^2). However, we can make the observation that whenever we visit an element, we don't need to check this element anymore in any of our future traversals. Therefore, we can try to erase this node in every visit. We can simply manage do this with a set.

Code:

// cool trick, thanks lunchbox & purple!!!

void solve(int test_case = 0)
{
    int n; cin >> n;
    int m; cin >> m;
    vector<set<int>> adj(n);
    set<int> toremove;
    queue<int> bfs;
    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        adj[x].insert(y);
        adj[y].insert(x);
    }
    vector<int> todo;
    for(int i = 0; i < n; ++i)
        toremove.insert(i);
    int ccs = 0;
    for(int i = 0; i < n; ++i) {
        if(toremove.count(i)) {
            bfs.push(i);
            ++ccs;
            toremove.erase(i);
            while(bfs.size()) {
                int x = bfs.front();
                bfs.pop();
                todo.clear();
                for(int j : toremove)
                    if(!adj[x].count(j)) 
                        todo.pb(j);
                for(int j : todo)
                    toremove.erase(j), bfs.push(j);
                
            }       
        }
    }
 
    cout << ccs - 1 << "\n";
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    // C++ IO Stuff
    int T = 1;
#ifdef runcase
    cin >> T;
#endif
    // new test cases
    for(int nt = 0, i; nt < T; nt++) {
        solve(nt);
        ++i;
    }
}

Explanation: This is ordinary BFS, except we need to erase our node once we visit. However, we cannot simply erase this element from the set as we are traversing, so we need an extra array that will store our information for us (our what we have to-do). We will erase this information subsequently. Despite this, queue traversal is simple and checking if our element is in the set is the same as using a visited array. Our code is now at complexity O(N log N + N log M) because of our array of sets, and our insertion, erase, and count functions on the set we use to check for nodes (toremove). Submit!

Example Submission: 120517490

Other problems to try:

https://codeforces.me/contest/190/problem/E

http://www.usaco.org/index.php?page=viewproblem2&cpid=765

https://codeforces.me/contest/1508/problem/C

Thanks for viewing!

Lol