Medium – Hard
Split Graph, Degree Sequence, Quick Sort.
Given an undirected graph with n nodes and m edges, check whether this graph can be partitioned into two node sets such that one the induced graph is a clique and the other is an independent set.
This type of graph is a special graph called Split Graph. There is a conclusion to check the feasibility – Degree Sequence. That is:
Let the degree sequence of a graph G be d_1≥d_2≥⋯≥d_n, and let m be the largest value of i such that d_i≥i-1. Then G is a split graph if and only if
See Wiki Pedia for more details:
With this property, we can easily check this problem in O(m+nlogn) time using quick sort.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.