PROBLEM LINK: Human Ghoul Neighbouring
Author: ponder
DIFFICULTY:
SIMPLE
PREREQUISITES:
GRAPH THEORY,DFS
PROBLEM:
Given N houses connected by N-1 roads, we need to construct the maximum number new roads between houses without breaking the rule that there should not a direct road between the houses of same species.
EXPLANATION:
From the rule given in the question it was clear that it is the property of bipartite graph! The given graph is of tree and you need to find the number of more edges you can add so that the graph still remain bipartite. Approach : Color the tree with two color and find the number of nodes with color HUMAN and number of nodes with color GHOUL once you have this number then you can say that HUMAN x GHOUL
number of maximum edge will that graph have! Initially n-1
edge was given and if we subtract n-1
from HUMAN x GHOUL
then we will get our answer!
SOLUTIONS:
Setter's Solution
void dfs(int u, vvi &g, vi &species, int type) {
species[u] = type;
for(auto kid : g[u]) {
if(species[kid] == -1)
dfs(kid,g,species,!type);
}
}
void solve() {
int n,u,v; cin >> n;
vvi g(n+1);
FOR(i,n-1) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
vi species(n+1,-1);
dfs(1,g,species,0);
int human_cnt = 0, ghoul_cnt = 0;
rep(i,1,n+1) {
if(species[i]) ghoul_cnt++;
else human_cnt++;
}
// additional edge = total_edge_possible_in_bipartile_graph - existing_number_of_edge
cout << (ll)human_cnt * (ll)ghoul_cnt - (n-1);
}