Problem : Break The Friendship
In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was
able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.
Input Format:
Input consists of two parts, viz.
1. First Line contains, number of students in the class room (N) and number of friendship connections (M)
2. Next M line contains a list that represents two integers i and j, which represents that i and j are friends
Output Format:
Print "Yes" if the committee can divide the students in two groups of people, else print "No".
Constraints:
1 <= N <= 50
1 <= M <= N * (N1)/2
1 <= I, j <= N
Sample Input
4 3
1 2
1 3
2 4
Sample Output
Yes
In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was
able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.
Input Format:
Input consists of two parts, viz.
1. First Line contains, number of students in the class room (N) and number of friendship connections (M)
2. Next M line contains a list that represents two integers i and j, which represents that i and j are friends
Output Format:
Print "Yes" if the committee can divide the students in two groups of people, else print "No".
Constraints:
1 <= N <= 50
1 <= M <= N * (N1)/2
1 <= I, j <= N
Sample Input
4 3
1 2
1 3
2 4
Sample Output
Yes
Python Implementation:
friends,connections = map(int,raw_input().split(' '))
a=[]
b=[]
result = True
while connections>0:
i,j = map(int,raw_input().split(' '))
if i not in a and i not in b:
if j not in a and j not in b:
a.append(i)
b.append(j)
else:
if j in a:
b.append(i)
else:
a.append(i)
else:
if i in a:
if j in a:
result = False
else:
if j not in b:
b.append(j)
else:
if j in b:
result = False
else:
if j not in a:
a.append(j)
connections -= 1
if result:
print "Yes"
else:
print "No"
Other Problems from TCS Mockvita - 1 and Mockvita - 2:
Solution : MockVita-I Problem D
Solution : MockVita-II Problem C
Solution : MockVita-II Problem B
Solution : MockVita-II Problem D
Solution : MockVita-II Problem A
Solution : MockVita-I Problem B
Solution : MockVita-I Problem C
Solution : MockVita-I Problem F
Solution : MockVita-I Problem A