Greedy Maximum Independent Set Approximation

You are given an undirected graph. Your task is to compute an approximation of the maximum independent set using a greedy algorithm. An independent set \(S\) of a graph \(G=(V,E)\) satisfies the condition that for every edge \((u,v)\in E\), at least one of \(u\) or \(v\) is not in \(S\), i.e. \(\forall (u,v)\in E,\; u\notin S \quad\text{or}\quad v\notin S\). The algorithm sorts the vertices by increasing degree and then iteratively selects a vertex if it has not already been excluded by a neighbor. This provides an approximation to the maximum independent set.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of vertices and \(m\) is the number of edges. The next \(m\) lines each contain two integers \(u\) and \(v\) representing an undirected edge between vertices \(u\) and \(v\). The vertices are numbered from 0 to \(n-1\).

outputFormat

Output the vertices in the independent set found by the greedy algorithm in ascending order, separated by a space. If the set is empty, output an empty line.

5 7
0 1
0 3
1 3
2 0
2 3
2 4
3 4

1 4