In this HackerEarth Visiting friends problem solution M friendships exist between N people. They are divided into groups such that all the friends will remain in same group and the people from each group visit each other according to the following conditions:
  1. Each people can host only one other people from their group.
  2. Each people can visit only one other people from their group.
  3. Friendship is transitive in nature, which means, if A is a friend of B and B is a friend of C then A is also a friend of C.
Write a program to find the number of ways in which the people from each group can visit each other. Two ways are considered different if at least one people visits two different friends.

HackerEarth Visiting friends problem solution


HackerEarth Visiting friends problem solution.

#include <bits/stdc++.h>

using namespace std;

long long dp [100000 + 10];
vector < int > arr [100000 + 10];
vector < int > v;
vector < long long > res;
bool vis [20 + 10];
int ans = 0;


void dfs(int index){

vis[index] = true;

for(int i = 0; i < arr[index].size(); i++){

int e = arr[index][i];
if(!vis[e]) dfs(e);
}

v.push_back(index);
}

void dfs2(int index){

vis[index] = true;
ans++;

for(int i =0; i < arr[index].size(); i++){

int e = arr[index][i];
if(!vis[e]) dfs2(e);
}
}

void derange(){

dp[1] = 0; dp[2] = 1;

for(int i = 3; i <= 100000; i++){

long long num = i - 1;

dp[i] = num * (dp[i - 1] + dp[i - 2]);
}
}

int main()
{
int t , n, m, tem1, tem2;

derange();

scanf("%d", &t);

while(t--){

memset(vis, false, sizeof vis);
res.clear();
v.clear();
for(int i = 0; i <= 20; i++) arr[i].clear();

scanf("%d%d", &n, &m);

for(int i = 0; i < m; i++){

scanf("%d%d", &tem1, &tem2);
arr[tem1].push_back(tem2);
arr[tem2].push_back(tem1);
}

for(int i = 1; i <= n; i++){

if(!vis[i]) dfs(i);
}

reverse(v.begin(), v.end());
memset(vis, false, sizeof vis);

for(int i = 0; i < (int) v.size(); i++){

if(!vis[ v[i] ]){

ans = 0;
dfs2( v[i] );
long long push = dp[ans];
res.push_back(push);
}
}

printf("%d\n", (int) res.size());

sort(res.rbegin(), res.rend());

for(int i = 0; i < (int) res.size(); i++) printf("%lld ", res[i]);

printf("\n");
}

return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define PII pair<int,int>
#define all(c) c.begin(),c.end()
#define sz(c) (int)c.size()
#define clr(c) c.clear()
#define pb push_back
#define mp make_pair
#define cin(x) scanf("%d",&x)
#define MOD 1000000007
#define EPS 1E-10

int parent[21];
int size[21];

int FIND(int x)
{
if(parent[x] != x)
parent[x] = FIND(parent[x]);
return parent[x];
}

LL dp[50];

void solve()
{
int n,m;
cin(n);
cin(m);
assert(1 <= n && n <= 20);
assert(1 <= m && m <= (n*n));

for(int i = 0; i <= 20; i++)
{
parent[i] = i;
size[i] = 1;
}

while(m--)
{
int a,b;
cin(a);
cin(b);
assert(1 <= a && a <= n);
assert(1 <= b && b <= n);
int p1 = FIND(a);
int p2 = FIND(b);

if(p1 == p2) continue;
parent[p1] = p2;
size[p2] += size[p1];
}

vector<LL> arr;
for(int i = 1; i <= n; i++)
if(parent[i] == i)
arr.pb(dp[size[i]]);
cout << sz(arr) << "\n";
sort(all(arr));
reverse(all(arr));
for(int i = 0; i < sz(arr); i++)
cout << arr[i] << " ";
cout << "\n";
}

int main()
{
dp[0] = 1;
for(int i = 1; i <= 30; i++)
dp[i] = 1LL * (i - 1) * (dp[i-1] + dp[i-2]);
int t;
cin(t);
assert(1 <= t && t <= 100000);
while(t--)
solve();
return 0;
}