HackerEarth Visiting friends problem solution

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.

#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;
}