Блог пользователя tdpencil

Автор tdpencil, история, 3 года назад, По-английски

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.com/contest/190/problem/E

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

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

Thanks for viewing!

Lol

  • Проголосовать: нравится
  • +107
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

omg nice trick!

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Here's a problem that you need to use a similar trick for.

Though when I did it I avoided using a set. Instead, I'd maintain something similar to a linked list where each node that's still being considered can be used to find the next nodes before and after it that are also being considered. To remove a node from the list, you just connect the node before it and after it together in O(1) time. You'd also need to keep track of the first unused element as well, but that's simple enough.

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

"BFS on complement" is a better name for this. 1477D - Nezzar and Hidden Permutations is another problem where it is useful.

It's also worth noting that there are several ways to avoid the $$$\log n$$$ factor from using std::set if further optimizations are necessary. One that I've thought about which should be very fast for the common competitive programming situation of subsets of [1..n] or [0..n-1] is to use two mutable arrays p and pinv and an integer size to represent the set. p stores a permutation, pinv its inverse permutation (to allow fast lookup), and the first size elements of p are the set's elements (to allow fast iteration). Insertion and deletion can be achieved in $$$O(1)$$$ with a couple of swaps.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I got to know this trick while solving this problem

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

This ‘trick’ is very cool; we know this idea from a (very nice, in my opinion) problem in Romania:

https://infoarena.ro/problema/centrale

The statement is in Romanian, but you might be able to translate it.

The idea is to simulate a DFS in sub-linear time (in the number of edges) using some problem-specific Data Structure, therefore you can implement Kosaraju’s SCC algorithm and simulate 2SAT on such dense graphs.

I’ve used this trick several times in problems already (lots of times as a no-brainer alternative solution for hard problems).

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

[DELETED]

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/problemset/problem/920/E is this problem also solved using this ?