Forming Teams (Codeforces)

B. Forming Teams

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student A is an archenemy to student B, then student B is an archenemy to student A.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

Input

The first line contains two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of students and the number of pairs of archenemies correspondingly.

Next m lines describe enmity between students. Each enmity is described as two numbers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to n.

Output

Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

Sample test(s)

input

5 4
1 2
2 4
5 3
1 4

output

1

input

6 2
1 4
3 4

output

0

input

6 6
1 2
2 3
3 1
4 5
5 6
6 4

output

2

Tạm hiểu:
Có n sinh viên, cần chia làm hai đội có số người bằng nhau, trong đó có những sinh viên có thù hằn với nhau, yêu cầu trong một đội không có hai sinh viên có thù hằn. Nếu một sinh viên không được vào đội nào thì phải ngồi trên ghế. Tính số sinh viên phải ngồi trên ghế.

Solution:
Sử dụng cấu trúc Disjoint set để giải quyết bài toán này, nếu hai thằng chung gốc và là lẻ thì chắc chắn sẽ  bỏ đi 1 thằng. Sau đó nếu số sinh viên còn lại là số lẻ thì bỏ thêm 1 thằng nữa.
Code:


#include<iostream>
#include<cstdio>
using namespace std;
int N,M;
int p[101];
int e[101];
int res=0;

int FindSet(int x);

int main()
{
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
cin >> N >> M;
for(int i=1;i<=N;i++) p[i]=i,e[i]=1;

int x,y;
for(int i=0;i<M;i++)
{
scanf("%d%d",&x,&y);
int px = FindSet(x),py=FindSet(y);
if((px==py)&&(e[py]&1))
res++;
p[px]=p[y];e[py]+=e[px];
}
if((N-res)%2!=0)
res++;
cout << res;
return 0;
}

int FindSet(int x)
{
if(x!=p[x])return FindSet(p[x]);
return x;
}