Editorial for Spooky Hallways
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Editorialist:
Spooky hallways is a problem in which you have to find a way to all the nodes of a graph using each edge once. This is very similar to the famous Seven Bridges of Königsberg problem, which was solved by Euler with his Eulerian path. We can use a similar technique here.
A path is not an Eulerian path if any vertex has an odd number of edges leaving it. We can use this property to find the minimum number of new hallways that need to be built in order by counting the number of vertexes with an odd number of connections, dividing by two and then outputting the answer.
#include <bits/stdc++.h>
using namespace std;
int n_halls[2000];
void solve() {
fill_n(n_halls, 2000, 0);
int N, M;
cin >> N >> M;
for (int m = 0; m < M; ++m) {
int u, v;
cin >> u >> v;
n_halls[u-1]++;
n_halls[v-1]++;
}
int inc = 0;
int n_extra = 0;
for (int i = 0; i < N; ++i) {
if (n_halls[i]&1) { // is odd
if (n_extra)
--n_extra;
else {
++inc;
++n_extra;
}
}
}
cout << inc << endl;
}
int main() {
int T;
cin >> T;
for (int t = 0; t < T; ++t) {
solve();
}
}
Comments