Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1886
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1886
Protecting the Temples
By Renzo Gonzalo Gómez Diaz, Universidade de São Paulo 
Brazil
Timelimit: 1
There are thousands of Buddhist temples in Thailand, known as "wat". Some of them, such as the "Wat Phra Kaew" in Bangkok's Grand Palace, are specially regarded for their importance and they're called royal temples. The "Wat Phra Kaew" is famous for housing the Emerald Buddha statue, a national treasure. In 2016, the ACM ICPC World Finals will take place in Phuket, Thailand, and so increased tourism is expected in this city. The authorities in Phuket thus want to improve security in its royal temples.
Phuket's Security Unit (PSU) hired the researcher Lua "the ingenious" Kuratowski. PSU needs to solve the following problem. Given N royal temples and M streets connecting them, they must position guards at these streets so that every royal temple can be under surveillance. They consider a temple as secured if there is a guard in at least one of the streets ending at the temple. Streets were laid out so that one can reach any temple from any other. Moreover, due to a cultural dislike of odd numbers, any time someone starts a walk at a temple and returns to it, the number of streets traversed is always even.
Lua knows you wish to advance to the World Finals next year, and she considers this to be a good test for your skills. She challenges you to find a solution with the minimum number of guards.
Input
The input is composed of many instances. The first line of the input contains an integer T which indicates the number of instances.
Each instance spans several input lines. The first line has two integers, N (1 ≤ N ≤ 103) and M (1 ≤ M ≤ 5*103), the number of royal temples and the number of streets joining temples, respectively. Each temple is represented by an integer between 1 and N. The next M lines describe the streets. Each street is represented by two integers, corresponding to the temples it joins.
Output
For each instance, print a single line with the minimum number of guards needed to have all royal temples under surveillance.
| Input Sample | Output Sample |
|
2 |
3 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int vis[1005];
int freq[2];
vector < vector<int> > v;
void dfs(int n, int cor)
{
vis[n] = cor;
++freq[cor];
for (int i = 0 ; i < (int)v[n].size(); ++i)
if (vis[v[n][i]] == -1) dfs(v[n][i], cor ^ 1);
}
int main()
{
ios_base :: sync_with_stdio(0); cin.tie(0);
int n, m;
int u, v1;
int cases;
cin >> cases;
while (cases--)
{
cin >> n >> m;
v.assign(n, vector<int>());
for (int i = 0 ; i < m; ++i)
{
cin >> u >> v1;
--u;
--v1;
v[u].push_back(v1);
v[v1].push_back(u);
}
freq[0] = freq[1] = 0;
for (int i = 0 ; i < n ; ++i) vis[i] = -1;
dfs(0, 0);
cout << max(freq[0], freq[1]) << '\n';
}
}
Input
5 5
1 2
1 4
2 3
4 3
3 5
4 3
1 2
1 3
1 4
Output
3