CODEWITHSUNDEEP
algorithmgraph
Peter
Peter

Reputation: 2759

Algorithm: Explanation of a graph based

In Futaba Kindergarten, where Shinchan studies, there are N students, s_0, s_1...s_(N-1), including Shinchan. Every student knows each other directly or indirectly. Two students knows each other directly if they are friends. Indirectly knowing each other means there is a third students who knows both of them. Knowing each other is a symmetric relation, i.e., if student s_a knows student s_b then student s_b also knows student s_a.

Ai-chan is a new admission in the class. She wants to be friend with all of them. But it will be very cumbersome to befriend each of the N students there. So she decided to befriend some of them such that every student in the class is either a friend of her or friend of friend of her.

Help her to select those students such that befriending them will complete her objective. The lesser number of students the better it is.

Input

First line of input will contain two space separated integer, N M, number of students at Futaba Kindergarten, excluding Ai-chan, and number of pairs of students who are friend to each other, i.e. they knows each other directly. Then follows M lines. In each line there are two space separated integer, s_u s_v, such that student s_u and s_v are friend to each other.

Output

In first line print the total number, P, of such students. Then in next line print P space separated index of students, such that befriending them will help Ai-chan to achieve her objective.

Constraints:

1 <= N <= 10^5

1 <= M <= min(10^5, N*(N-1)/2)

0 <= s_u, s_v <= N-1

s_u != s_v

Each pair of students (s_u, s_v) knows each other, directly or indirectly.

Score: ((N-P)/N)*200

**Sample Input**
6 7
0 1
0 2
1 2
1 3
2 4
3 4
3 5

**Sample Output**
4
0 2 3 5

Im My opinion be friending with only 1 and 3 will do the job. Am i missing something ? I am not looking for the solution , just the explanation of sample input and output.

Upvotes: 0

Views: 150

Answers (1)

orezvani
orezvani

Reputation: 3785

The solution is a simple greedy algorithm. Suppose that C is the set of students.

S = {}
R = {}
while (C != {}) {
   - sort the students based on their number of friends
   - pick the student s with the highest number of friends
   - add R = R + {s}
   - add s and friends of s to the set S and remove them from C
}
print(R)

Upvotes: -1

Related Questions