Guni¶

Application¶

In many problems, a "guni" can be used (several examples are given in this chapter's exercises). But to better clarify this concept and its importance, we'll solve an example together. In this problem, we have a rooted tree where each vertex has a color. For every subtree, we want to calculate and output the number of distinct colors. Assume you know the guni problem's solution and try to solve this problem using it.

To solve this problem, we use a data structure that can: 1. Add a vertex 2. Remove a vertex 3. Return the count of distinct colors

This data structure can be a simple array where: - When adding a vertex, we increment the corresponding color's cell by 1 - When removing a vertex, we decrement the corresponding color's cell by 1 - We simultaneously maintain a distinct color counter (i.e., if a color's count changes from 0 to 1 when added, we increment the counter; if it changes to 0 when removed, we decrement the counter)

All three operations in this data structure run in \(O(1)\) time.

Now we use the guni algorithm (whose implementation details we currently don't know). We process all subtrees once in this data structure, record their answers, then print the results.

Algorithm¶

The idea of the sack is similar to the heavy-light separation idea introduced in the chapter on Lowest Common Ancestor (LCA). (For a reminder, you can refer to Section 10.2). Our goal is to perform operations on each vertex proportional to the number of its light edges in the path to the root. That is, the total number of deletions and additions of vertex \(v\) to the sack during all operations should be \(O(light_v)\). From Section 10.2, we recall that \(light_v \le \lg(n)\), so if we succeed in this, the total operations across all vertices will be \(O(n \lg(n))\).

We implement the algorithm as a recursive function. This function takes an input vertex, starts with an empty sack, places all subtrees rooted under this vertex into the sack once, then returns the sack containing all vertices of its subtree. Implementing this function is trivial for a leaf node and runs in constant time. For non-leaf vertices, we proceed recursively. First, we execute the function on all light-edge children and empty the sack after each execution. Next, we execute the function on the heavy-edge child of this vertex without emptying the sack, then re-add the light-edge children to the sack. Now the entire subtree is in the sack. We retrieve the answer for the input vertex from the data structure and terminate the function.

During execution, all children of the heavy-edge vertex are only added to or removed from the sack as required by the recursive function, while light-edge children are removed once and re-added once by the main function. The input vertex itself is also added once at the end. It can be observed that the total number of additions and removals for any vertex \(v\) is exactly \(2 light_v + 1\). Additionally, the runtime of the algorithm is proportional to the number of sack operations, and both—as explained above—are \(O(n \lg(n))\).

Implementation¶

This section discusses the implementation of graph algorithms. Below is an example code block for checking bipartiteness:

 1def is_bipartite(g):
 2    # In this problem, we assume the graph is undirected
 3    color = {}
 4    for node in g.nodes():
 5        if node not in color:
 6            queue = [node]
 7            color[node] = 0
 8            while queue:
 9                v = queue.pop(0)
10                for neighbor in g.neighbors(v):
11                    if neighbor in color:
12                        if color[neighbor] == color[v]:
13                            return False
14                    else:
15                        color[neighbor] = 1 - color[v]
16                        queue.append(neighbor)
17    return True

Another example with adjacency matrix representation:

 1def has_cycle(matrix):
 2    # Detects cycles in undirected graphs using DFS
 3    visited = [False] * len(matrix)
 4    for i in range(len(matrix)):
 5        if not visited[i]:
 6            stack = [(i, -1)]
 7            while stack:
 8                node, parent = stack.pop()
 9                visited[node] = True
10                for j in range(len(matrix[node])):
11                    if matrix[node][j]:
12                        if not visited[j]:
13                            stack.append((j, node))
14                        elif j != parent:
15                            return True
16    return False

Key points to remember:

1. Always handle disconnected graphs

2. Choose appropriate data structures based on graph density

3. Consider edge cases like empty graphs and single-node graphs

const int M = 1e5 + 5;
vector<int> g[M];
int sz[M]; // andaaze zirderakht har ras, baraaye tashkhis yaal haaye sabok va sangin

void add_to_gooni(int v) {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}
void remove_from_gooni(int v) {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}
void compute_answer() {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}

void add_subtree(int v, int p){
    add_to_gooni(v);
    for(int u: g[v])
        if(u != p)
            add_subtree(u, v);
}
void remove_subtree(int v, int p){
    remove_from_gooni(v);
    for(int u: g[v])
        if(u != p)
            add_subtree(u, v);
}

void dfs(int v, int p){
    int mx = -1, bigChild = -1;
    for(int u : g[v]) {
      if(u != p && sz[u] > mx) {
        mx = sz[u];
        bigChild = u;
      }
    }
    for(int u : g[v]) {
      if(u != p && u != bigChild) {
        dfs(u, v); // javaabe farzand haye sabok ra mohaasebe mikonim
        remove_subtree(v, p); // sepas aan haa raa paak mikonim
      }
    }
    if(bigChild != -1)
        dfs(bigChild, v);  // farzande sangin raa paak nemikonim
    for(auto u : g[v]) {
      if(u != p && u != bigChild)
        add_subtree(u, v); // farzand haye sabok ra mojadadan bar migardaanim
    }
    compute_answer(); // hame zirderakht v dar gooni ast, javabash ra hesab mikonim
}

1# درخت DFS ریشه‌دار بسازید
2def dfs(u, parent):
3    sz[u] = 1  # اندازه زیردرخت اولیه
4    for v in graph[u]:
5        if v != parent:
6            dfs(v, u)
7            sz[u] += sz[v]  # افزودن اندازه زیردرخت فرزند

توضیحات: - در خط ۴، حلقه روی همسایه‌های رأس u اجرا می‌شود. - شرط v != parent از بازگشت به والد جلوگیری می‌کند. - در خط ۶، اندازه زیردرخت فرزند به والد اضافه می‌شود.

نکته: الگوریتم فوق اندازه زیردرخت هر رأس را در آرایه sz ذخیره می‌کند. برای پر کردن این آرایه با روش‌های دیگر (مثلاً BFS)، نیاز به تغییر الگوریتم دارید.