If the length of the given string $$$s$$$ is odd, then the answer is $$$NO$$$, since it cannot be a concatenation of two equal strings. Otherwise, Let's slice the string into equal halves. If the two halves are equal the answer is $$$YES$$$, otherwise $$$NO$$$.

t = int(input())
for _ in range(t):
    s = input()

    if len(s)%2:
        print('NO')
    
    else:
        mid = len(s)//2
        print('YES' if s[:mid] == s[mid:] else 'NO')
        

Treat the forest as a union-find data structure.

The key observation is that each baboon and its most distant relative on the same tree belong to the same tree (connected component). We can use this fact to identify the number of trees.

Solution Approach:

We can use a Union-Find data structure to efficiently group relative baboons in a single tree. Initialize a union-find object with $$$n$$$ baboons (one for each baboon) Iterate through the sequences $$$s$$$. For each baboon $$$i$$$, perform a union operation on $$$i$$$ and $$$(s[i] - 1)$$$. This connects baboon $$$i$$$ with its most distant relative. Count the number of unique representatives in the union-find. That will be the answer.

Time & Space Complexity

Time Complexity: $$$O(n)$$$, where $$$n$$$ is the number of baboons. This is due to the single loop for processing the $$$s$$$ sequence and another loop for finding representatives. Space Complexity: $$$O(n)$$$, due to the Union-Find data structure and the set used to store representatives.

from collections import defaultdict
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def find(self, x):
        while x != self.root[x]:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return x
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.size[rootX] > self.size[rootY]:
                self.root[rootY] = rootX
                self.size[rootX] += self.size[rootY]
            else:
                self.root[rootX] = rootY
                self.size[rootY] += self.size[rootX]


def main():
    n = int(input())
    seq = list(map(int, input().split()))
    forest  = UnionFind(n)
    for i in range(n):
        forest.union(i, seq[i] - 1)
    
    tree_numbers = set()
    for i in range(n):
        tree_numbers.add(forest.find(i))
    
    print(len(tree_numbers))

if __name__ == '__main__':
    main()

To track the valid parenthesis strings, we can use a stack. When encountering an opening bracket $$$($$$, we add its index to the stack. If it's a closing bracket $$$)$$$, we remove the last unpaired opening bracket. Whenever we remove the index of an opening bracket $$$i$$$, we can observe that the substring from $$$s_i$$$ to the current index forms a balanced bracket sequence. This is because when we remove an unpaired opening bracket, the substring between the removed index and the current index has matching opening and closing brackets. Thus, we unite the two indices to mark this valid substring as part of the connected components in Athanasius's graph. This process ensures that we account for all balanced bracket sequences in the graph construction. Additionally, if the current bracket is a closing bracket $$$)$$$ and the next bracket (current index plus one) is an opening bracket $$$($$$, we unite them. This is because the current bracket marks the end of a balanced bracket sequence, and the next bracket marks the start of another balanced bracket sequence, and two balanced brackets together form a balanced bracket sequence.

class UnionFind:
	def __init__(self, size):
    		self.parent = list(range(size))
    		self.rank = [0] * size

	def find(self, element):
            if self.parent[element] != element:
                    self.parent[element] = self.find(self.parent[element])
            return self.parent[element]

	def union(self, element_a, element_b):
            root_a, root_b = self.find(element_a), self.find(element_b)
            if root_a != root_b:
                if self.rank[root_a] > self.rank[root_b]:
                    self.parent[root_b] = root_a
                elif self.rank[root_a] < self.rank[root_b]:
                    self.parent[root_a] = root_b
                else:
                    self.parent[root_a] = root_b
                    self.rank[root_b] += 1

def solve():
	num_pairs = int(input())
	brackets = input().strip()
	uf = UnionFind(2 * num_pairs)
	stack = []
	for i, bracket in enumerate(brackets):
            if bracket == "(":
                    stack.append(i)
            else:
                top = stack.pop()
                uf.union(i, top)
                if i + 1 < 2 * num_pairs and brackets[i + 1] == "(":
                    uf.union(i, i + 1)
	num_connected_components = sum(1 for i, parent in enumerate(uf.parent) if i == parent)
	print(num_connected_components)

num_tests = int(input())
for _ in range(num_tests):
	solve()

In this problem we are given a disjoint set union process with $$$n−1$$$ steps, merging $$$n$$$ initial $$$1$$$-element sets into one $$$n$$$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).

This problem can be solved in $$$O(nlogn)$$$ via standard disjoint-set data structure, additionally storing lists of elements in each set.

The simplest solution is storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements when we have to merge two sets A and B, we make the smaller set part of the larger set and update mappings and concatenating the lists can be done in $$$O(min(|A|,|B|)))$$$.

This gives us $$$O(nlogn)$$$: element can not change its set more than $$$logn$$$ times, because the change leads to (at least) doubling of the element's set size.

import sys
n = int(sys.stdin.readline().strip())
parent = {}
elem = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    elem[i].append(i)
    parent[i] = i
size = [1] * (n + 1)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    par_x = find(x)
    par_y = find(y) 
    if par_x != par_y:
        if size[par_x] >  size[par_y]:
            parent[par_y] = par_x
            elem[par_x].extend(elem[par_y])
            size[par_x] += size[par_y]
        else:
            parent[par_x] = par_y
            elem[par_y].extend(elem[par_x])
            size[par_y] += size[par_x]
for _ in range(n - 1):
    x, y = map(int, sys.stdin.readline().strip().split())
    union(x, y)

print(*elem[find(1)])

Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.

from collections import defaultdict
from sys import stdin


def input(): return stdin.readline().strip()

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v
    
    def merge(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.p[pv] = pu
        return True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    edges = []
    adj = defaultdict(list)
    for __ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edges.append((w, u, v))
        adj[u].append(v)
        adj[v].append(u)

    edges.sort(key=lambda edge: edge[0], reverse=True)
    dsu = DSU(N)
    for w, u, v in edges:
        if not dsu.merge(u, v):
            ans = (w, u, v)

    min_w, st, end = ans
    stk = [st]


    # DFS to get the cycle
    p = [-1]*N
    p[st] = st
    while stk:
        v = stk.pop()
        for ch in adj[v]:
            if v == st and ch == end: continue
            if ch == end:
                p[ch] = v
                stk = []
                break
            if p[ch] == -1:
                p[ch] = v
                stk.append(ch)
    v = end
    path = []
    while p[v] != v:
        path.append(v)
        v = p[v]
    path.append(st)

    print(min_w, len(path))
    for i in range(len(path)):
        path[i] += 1
    print(*path)