Problem - K - Codeforces

To solve this problem, we need to determine if the students can be partitioned into two sets, A and B, such that A forms a complete subgraph (clique) and B forms an independent set (no edges between any two nodes in B). This problem can be efficiently solved by checking if the given graph is a split graph, which can be determined by analyzing the degree sequence of the graph.

Approach

  1. Degree Sequence Analysis: The degree sequence of a graph is a list of degrees of the nodes in non-increasing order. For a graph to be a split graph, there exists a partition of the nodes into a clique (A) and an independent set (B). This can be checked using the degree sequence.
  2. Check Split Graph Condition:
    • Sorting the degree sequence in non-increasing order.
    • Finding the largest integer k such that the first k nodes form a clique and the remaining nodes form an independent set.
    • Verifying if the sum of degrees of the first k nodes matches the expected sum for a clique and the remaining nodes’ degrees match the sum for an independent set.

Solution Code

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    
    degrees = [0] * (N + 1)  # degrees[1..N]
    for _ in range(M):
        u = int(input[idx])
        idx += 1
        v = int(input[idx])
        idx += 1
        degrees[u] += 1
        degrees[v] += 1
    
    degrees = degrees[1:N+1]
    degrees.sort(reverse=True)
    n = N
    max_k = 0
    for k in range(1, n + 1):
        # Check if d[k-1] >= k-1
        if degrees[k-1] < k-1:
            continue
        # Check if d[k] <= k-1 when k < n
        if k < n and degrees[k] > k-1:
            continue
        max_k = k
    
    if max_k == 0:
        print("NO")
        return
    
    sum_degrees = sum(degrees[:max_k])
    sum_rest = sum(degrees[max_k:])
    expected = max_k * (max_k - 1) + sum_rest
    if sum_degrees == expected:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

Explanation

  1. Reading Input: The input is read and parsed to get the number of students (N) and the number of edges (M). The degrees of each node are calculated based on the edges.
  2. Sorting Degrees: The degrees are sorted in non-increasing order to facilitate the split graph check.
  3. Finding Maximum k: The largest k is determined such that the first k nodes can potentially form a clique and the remaining nodes form an independent set.
  4. Verifying Conditions: The sum of the degrees of the first k nodes is checked against the expected sum for a clique, and the sum of the remaining nodes’ degrees is checked against the expected sum for an independent set. If both conditions are satisfied, the graph is a split graph, and the answer is “YES”; otherwise, it is “NO”.

This approach efficiently checks the necessary conditions for the graph to be a split graph using properties of the degree sequence, ensuring a solution with a time complexity of O(N log N) due to the sorting step.