Answer to Question #274500 in C for Rahul Sigh

Question

Good character

You are given a tree with N nodes and N-l edges and two nodes x and y where x! = y. Each node is assigned with a character from 'a' to 'z'. Let us define function F (c) as the total number of pairs of nodes (u,v) such that the shortest path from node u to node v includes nodes x and y and characters present at nodes u and v are equal to c. You are given a string S where S[i]denotes the character assigned to node I where1≤ i ≤ N

Task

Determine the value of F(c) for all characters c from 'a' to 'z:

Notes

•   Pair (u, v) and pair (v, u) are considered the same.

•   Assume I-based indexing of string S.

Hint: In Trees, there is only one unique path between two nodes.

Answer 1

#include <iostream>
#include <queue>
#define V 4
using namespace std;
bool isBipartite(int G[][V], int src)
{
	int colorArr[V];
	for (int i = 0; i < V; ++i)
		colorArr[i] = -1;
	colorArr[src] = 1;
	queue <int> q;
	q.push(src);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		if (G[u][u] == 1)
		return false;
		for (int v = 0; v < V; ++v)
		{
			if (G[u][v] && colorArr[v] == -1)
			{
				colorArr[v] = 1 - colorArr[u];
				q.push(v);
			}
			else if (G[u][v] && colorArr[v] == colorArr[u])
				return false;
		}
	}
	return true;
}
int main()
{
	int G[][V] = {{0, 1, 0, 1},
		{1, 0, 1, 0},
		{0, 1, 0, 1},
		{1, 0, 1, 0}
	};
	isBipartite(G, 0) ? cout << "Yes" : cout << "No";
	return 0;
}