HACKEREARTH: Permutation Swaps

Link:- https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/permutation-swaps/

Summary:
Given P and Q be two permutation of numbers 1 to N. Given some pair of indexes (ai , bi).
Your task is to find Q from P by swapping (Pai , Pbi).
Print YES if it possible else print NO.

For Example:
Input:
2
4 1
1 3 2 4
1 4 2 3
3 4
4 1
1 3 2 4
1 4 2 3
2 4

Output:
NO
YES

Logic:
Use Breadth First Search(BFS) to find connected components of indexes.
Then check for indexes in each connected component if P and Q are same or not.

To View My Solution:
https://github.com/shivam04/codes/blob/master/hackerearth/algo/graph/medium/permutation-swaps.cpp

HACKEREARTH: Connected Horses

Link:- https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/connected-horses-10/description/

Summary:
Given N ,M number of rows and columns in a chess board
Given Q queries each query contain co-ordinates of horses in a chess board.
Find the number of ways horses swap their position

For Example:
Sample Input:
2 
4 4 4
1 1
1 2
3 1
3 2
4 4 4
1 1
1 2
3 1
4 4

Sample Output:
4
2

Topic:
Breadth First Search(BFS) , Dynamic Programming(DP)

Logic:
Use Breadth First Search(BFS) to find the total number of horses in each connected groups, then find the factorial of this number. Apply same in each group and multiplication of all gives the result. Use DP for calculation of factorials.

To View my solution:
https://github.com/shivam04/codes/blob/master/hackerearth/algo/graph/medium/connected-horses.cpp