 Author: ponder

SIMPLE

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);
}
``````
3 Likes

please make it available for practice

What is wrong with the following code? It gives WA

``````#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> edge(1e5 + 1);
vector<int> sp(1e5 + 1, -1);
int u = 0, v = 0;
void dfs(int cur, int level) {
sp[cur] = level;
if(level == 0) {
u ++;
} else {
v ++;
}
for(int i : edge[cur]) {
if(sp[i] == -1) {
dfs(i, !level);
}
}
}

int main() {
int N;
cin >> N;
int root = 0;
for(int i = 0; i < N - 1; i ++) {
int from, to;
cin >> from >> to;
if(i == 0) root = from;
edge[from].push_back(to);
edge[to].push_back(from);
}
dfs(root, 0);
cout << (u * v) - (N - 1) << endl;
return 0;
}``````