HackerEarth Ikshu and his class problem solution

In this HackerEarth Ikshu and his class problem solution, Ikshu’s class is very fond of playing games. Their teacher tied them with many ropes with each other, Such that each student is tied with exactly one rope. It means that if students 2 and 3 are connected and 2 is connected to 4 as well then 2,3 and 4 must be sharing the same rope.

Now, teacher asks them to divide themselves in group. One group for each rope, each group consists of the students tied to that particular rope. Each group exchanges gifts among themselves (each student is having exactly one gift before and after the game).

What is the total number of distinct exchanges possible? Two exchanges are distinct if there is at least one student having different gift with him.

NOTE: It is also possible that a student has same gift after exchanging as he had before exchanging. There might be a case where no exchange took place i.e each student is having same gift after exchanging as he was having before exchange.

HackerEarth Ikshu and his class problem solution.

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

#define MAX 100002
#define MOD 1000000007

long long  comp = 0;
vector<long long > G[MAX];
long long  visited[MAX];
long long  components[MAX];
long long  fact[MAX];

void cal_fact(){
    fact[0] = fact[1] = 1;
    for(long long  i=2;i<MAX;i++){
        fact[i] = i*fact[i-1];
        fact[i] %= MOD;
    }
}


void DFS(long long  node){
    components[comp]++;
    visited[node] = 1;
    for(long long  i=0;i<G[node].size();i++){
        if(!visited[G[node][i]]){
            DFS(G[node][i]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    memset(visited,0,sizeof(visited));
    memset(components,0,sizeof(components));
    cal_fact();
    long long  N,K;
    cin >> N >> K;
    for(long long  i=0;i<K;i++){
        long long  x,y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(long long  i=0;i<N;i++){
        if(!visited[i]){
            DFS(i);
            comp++;
        }
    }
    long long  ans = 1;
    for(long long  i=0;i<comp;i++){
        ans *= fact[components[i]];
        ans %= MOD;
    }
    cout << ans << endl;
}

Second solution

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<stdio.h>
#include<cassert>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pd(n) printf("%lf ",n);
#define pdl(n) printf("%lfn",n);
#define pin(n) printf("%dn",n)
#define pln(n) printf("%lldn",n)
#define mod (int)(1e9 + 7)
#define ll long long int
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} 
ll arr[100006],cnt[1000006];
//Finding parent using Disjoing Set Union(DSU)
ll find_parent(int node)
{
    while(arr[node]!=node)
    {
        arr[node]=arr[arr[node]];
        node=arr[node];
    }
    return node;
}
inline ll fact(ll val)
{
    ll calc=1,i;
    FOR(i,1,val+1)
    {
        calc*=i;
        if(calc>=mod)
            calc%=mod;
    }
    return calc;
}
int main()
{
    ll n,k,i,ans=1,a,b,calc,temp,calc1,calc2;
    sl(n);
    sl(k);

    assert(n>=1 && n<=100000);
    assert(k>=1 && k<=100000);

    FOR(i,0,n+1)
        arr[i]=i;
    rep(i,k)
    {
        sl(a);
        sl(b);
        assert(a>=0 && a<n);
        assert(b>=0 && b<n);
        
        //Doing union of both elements
        calc1=find_parent(a);
        calc2=find_parent(b);
        if(calc1==a)
        {
            temp=calc1;
            calc1=calc2;
            calc2=temp;
        }
        arr[calc2]=calc1;
    }
    FOR(i,0,n)
    {
        calc=find_parent(i);
        cnt[calc]++;
    }
    FOR(i,0,n)
    {
        ans*=fact(cnt[i]);
        if(ans>=mod)
            ans%=mod;
    }
    pln(ans);
    return 0;
}

coding problems solutions