In this post, we will solve HackerRank ByteLandian Tours Problem Solution.
The country of Byteland contains N cities and N – 1 bidirectional roads between them such that there is a path between any two cities. The cities are numbered (0,…,N – 1). The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built between any two “somewhat near” cities. Any two cities in Bytleland that can be reached by traveling on exactly two old roads are known as “somewhat near” each other.
Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?
Input Format
The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The following N – 1 lines contain the description of the roads. The ith line contains two integers ai and bi, meaning that there was originally a road connecting cities with numbers ai and bi.
Constraints
1 <= T <= 20
1 <= N <= 10000
0 <= ai,bi < N
Output Format
Output T lines, one corresponding to each test case containing the required answer for that test case. Since the answers can be huge, output them modulo 1000000007.
Sample Input
2
3
0 1
1 2
5
0 1
1 2
2 3
2 4
Sample Output
2
4
Explanation
For the first case, a new road was build between cities 0 and 2. Now, the salesman has two tour possibilities: 0-1-2-0 or 0-2-1-0.
ByteLandian Tours C Solution
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
typedef struct node{
int x;
struct node *next;
} node;
void add_edge(int x,int y);
void clean();
int d[10000],N;
long long fac[10001];
node *list[10000]={0};
int main(){
int T,x,y,n,c1,c2,i;
long long ans;
node *p;
fac[0]=fac[1]=1;
for(i=2;i<10001;i++)
fac[i]=i*fac[i-1]%MOD;
scanf("%d",&T);
while(T--){
ans=1;
n=0;
scanf("%d",&N);
for(i=0;i<N;i++)
d[i]=0;
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
add_edge(x,y);
d[x]++;
d[y]++;
}
for(i=0;i<N;i++)
if(d[i]!=1){
n++;
c1=c2=0;
for(p=list[i];p;p=p->next)
if(d[p->x]==1)
c1++;
else
c2++;
if(c2>2){
ans=0;
break;
}
else
ans=ans*fac[c1]%MOD;
}
if(n>1)
ans=2*ans%MOD;
printf("%lld\n",ans);
clean();
}
return 0;
}
void add_edge(int x,int y){
node *p1,*p2;
p1=(node*)malloc(sizeof(node));
p2=(node*)malloc(sizeof(node));
p1->x=y;
p1->next=list[x];
list[x]=p1;
p2->x=x;
p2->next=list[y];
list[y]=p2;
return;
}
void clean(){
node *p1,*p2;
int i;
for(i=0;i<N;i++)
if(list[i]){
p1=list[i];
while(p1){
p2=p1;
p1=p1->next;
free(p2);
}
list[i]=NULL;
}
return;
}
ByteLandian Tours C++ Solution
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define pb push_back
typedef long long ll;
int ri()
{
int x;
scanf("%d", &x);
return x;
}
const int N = 10000, MOD = 1000000007;
int fac[N];
vector<int> e[N];
int f(int n)
{
int path = n, ans = 1;
REP(i, n)
if (e[i].size() == 1)
path--;
REP(i, n)
if (e[i].size() > 1) {
int leaf = 0, inner = 0;
for (auto v: e[i])
if (e[v].size() == 1)
leaf++;
else
inner++;
if (inner > 2)
return 0;
ans = ll(ans)*fac[leaf]%MOD;
}
return path == 1 ? ans : ans*2%MOD;
}
int main()
{
for (int cc = ri(); cc--; ) {
int n = ri();
REP(i, n)
e[i].clear();
fac[0] = 1;
FOR(i, 1, n)
fac[i] = ll(fac[i-1])*i%MOD;
REP(i, n-1) {
int x = ri(), y = ri();
e[x].pb(y);
e[y].pb(x);
}
printf("%d\n", f(n));
}
}
ByteLandian Tours C Sharp Solution
using System;
using System.Collections.Generic;
using System.Text;
class Solution
{
public const int MaxN = 10000;
public const int Modulo = 1000000007;
public static long[] Factorial;
public static void Init()
{
// Init Factorial
Factorial = new long[MaxN+2];
Factorial[0] = 1;
for (int i = 1; i <= MaxN; i++)
Factorial[i] = Factorial[i - 1] * i % Modulo;
}
static void Main(string[] args)
{
StringBuilder sb = new StringBuilder();
Init();
int NumTests;
int.TryParse(Console.ReadLine(), out NumTests);
for (int t = 0; t < NumTests; t++)
{
Tree tree = new Tree();
sb.Append(tree.Solve()).AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
class Tree
{
int _numNodes;
int _numLeaves;
Node[] _nodes;
long Result = 1;
bool _updateResult;
public Tree()
{
int.TryParse(Console.ReadLine(), out _numNodes);
_numLeaves = 0;
//Initializing Nodes
_nodes = new Node[_numNodes];
for (int n = 0; n < _numNodes; n++)
_nodes[n] = new Node(n);
//Reading Edges
string[] input;
int i, j;
for (int edge = 0; edge < _numNodes - 1; edge++)
{
input = Console.ReadLine().Split();
int.TryParse(input[0], out i);
int.TryParse(input[1], out j);
_nodes[i].Neighbors.Add(j);
_nodes[j].Neighbors.Add(i);
}
}
public long Solve()
{
MarkLeaves();
foreach (Node n in _nodes)
if (!n.IsLeaf && FindNextInCentralPath(n) > 2)
return 0;
if (_numLeaves == _numNodes - 1)
return Result;
return 2*Result % Solution.Modulo;
}
private void MarkLeaves()
{
foreach (Node n in _nodes)
if (n.Neighbors.Count == 1)
{
n.IsLeaf = true;
_numLeaves++;
}
}
private int FindNextInCentralPath(Node n)
{
int NumLeaves = 0;
int NumNext = 0;
foreach (int neighbor in n.Neighbors)
if (!_nodes[neighbor].IsLeaf)
NumNext++;
else
NumLeaves++;
Result = Result * Solution.Factorial[NumLeaves] % Solution.Modulo;
return NumNext;
}
}
class Node
{
public bool IsLeaf;
public List<int> Neighbors;
public Node(int idx)
{
Neighbors = new List<int>();
}
}
ByteLandian Tours Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
private static final int MODULUS = 1000000007;
private static class Node {
Set<Node> neighbors = new HashSet<>();
}
/*
* Complete the bytelandianTours function below.
*/
static int bytelandianTours(int n, int[][] roads) {
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node();
}
for (int[] road : roads) {
nodes[road[0]].neighbors.add(nodes[road[1]]);
nodes[road[1]].neighbors.add(nodes[road[0]]);
}
long result = 1;
int nonLeaves = 0;
for (Node node : nodes) {
if (node.neighbors.size() > 1) {
nonLeaves++;
int leaves = leafNeighbors(node);
if (leaves + 2 < node.neighbors.size()) {
return 0;
} else {
// System.out.println(String.format("Multiplying by %d!", node.neighbors.size() - 2));
for (int i = 2; i <= leaves; i++) {
result = (result*i) % MODULUS;
}
}
}
}
if (nonLeaves > 1) {
result = (result*2) % MODULUS;
}
return (int) result;
}
private static int leafNeighbors(Node n) {
int leaves = 0;
for (Node other : n.neighbors) {
if (other.neighbors.size() == 1) {
leaves++;
}
}
return leaves;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
int[][] roads = new int[n-1][2];
for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
String[] roadsRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
roads[roadsRowItr][roadsColumnItr] = roadsItem;
}
}
int result = bytelandianTours(n, roads);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
ByteLandian Tours JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the bytelandianTours function below.
*/
const mod = 1000000007n;
function bytelandianTours(length, roads) {
if (length < 3) return 1;
const tree = Array.from({ length }, () => []);
for (const [a, b] of roads) {
tree[a].push(tree[b]);
tree[b].push(tree[a]);
}
// Get the tree without the leaves
const internals = tree.filter(a => a.length > 1);
// Get the leaves of that internal tree
const ends = internals.filter(a => a.filter(b => b.length > 1).length < 2);
// If this internal tree has branches (i.e. more than two leaves), then there is no solution
if (ends.length > 2) return 0;
const first = ends[0];
const last = ends[1] || first;
return Number(internals.reduce((acc, a) => acc * factorial(a.length - (a !== first) - (a !== last)) % mod, BigInt(ends.length)));
}
function factorial(n) {
if (!factorial[n]) factorial[n] = factorial(n - 1) * BigInt(n) % mod;
return factorial[n];
}
factorial[0] = factorial[1] = 1n;
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const n = parseInt(readLine(), 10);
let roads = Array(n-1);
for (let roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
roads[roadsRowItr] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
}
let result = bytelandianTours(n, roads);
ws.write(result + "\n");
}
ws.end();
}
ByteLandian Tours Python Solution
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'bytelandianTours' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. 2D_INTEGER_ARRAY roads
#
def bytelandianTours(n, roads):
if n <= 2:
return 1
m = 1000000007
nbr = list()
for i in range(n):
nbr.append(list())
for a,b in roads:
nbr[a].append(b)
nbr[b].append(a)
city = 0
if len(nbr[0]) == 1:
city = nbr[0][0]
nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
if len(nbr[nbr[city][0]]) == 1:
return math.factorial(len(nbr[city])) % m
if len(nbr[city]) > 2 and len(nbr[nbr[city][2]]) > 1:
return 0
if len(nbr[nbr[city][1]]) > 1:
next_route = nbr[city][1]
nbr[next_route].remove(city)
rslt = (2 * math.factorial(len(nbr[city]) - 2)) % m
else:
next_route = -1
rslt = (2 * math.factorial(len(nbr[city]) - 1)) % m
#print(city, nbr)
parent = city
city = nbr[city][0]
nbr[city].remove(parent)
while True:
nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
#print(city, nbr)
if len(nbr[nbr[city][0]]) == 1:
rslt = (rslt * (math.factorial(len(nbr[city])) %m)) %m
if next_route != -1:
city = next_route
next_route = -1
continue
else:
break
if len(nbr[city]) > 1 and len(nbr[nbr[city][1]]) > 1:
return 0
rslt = (rslt * (math.factorial(len(nbr[city])-1) %m)) %m
parent = city
city = nbr[city][0]
nbr[city].remove(parent)
return rslt
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
roads = []
for _ in range(n - 1):
roads.append(list(map(int, input().rstrip().split())))
result = bytelandianTours(n, roads)
fptr.write(str(result) + '\n')
fptr.close()