PROBLEM LINK:
Author: Abdullah Al Mahmud
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Medium – Hard
PREREQUISITES:
Split Graph, Degree Sequence, Quick Sort.
PROBLEM:
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.
EXPLANATION:
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:
http://en.wikipedia.org/wiki/Split_graph
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.