Niloy007

Teacher's Dilemma || Hackerrank

May 7th, 2020
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. const int mod = 1e9 + 7;
  4. const int MAX = 1e5 + 7;
  5. using namespace std;
  6.  
  7. int parent[MAX];
  8.  
  9. int find(int a) {
  10.     if(parent[a] < 0) {
  11.         return a;
  12.     } else {
  13.         return parent[a] =  find(parent[a]);
  14.     }
  15. }
  16.  
  17. void Union(int a, int b) {
  18.     parent[a] += parent[b];
  19.     parent[b] = a;
  20. }
  21.  
  22. int main() {
  23.     int n, m, u, v, a, b;
  24.     cin >> n >> m;
  25.  
  26.     for(int i = 0; i <= n; i++) {
  27.         parent[i] = -1;
  28.     }
  29.  
  30.     for(int i = 1; i <= n; i++) {
  31.         int a, b;
  32.         cin >> a >> b;
  33.         a = find(a);
  34.         b = find(b);
  35.         if(a != b) {
  36.             Union(a, b);
  37.         }
  38.     }
  39.  
  40.  
  41.     long long int mul = 1;
  42.  
  43.     for (int i = 1; i <= n; i++) {
  44.         if(parent[i] < 0) {
  45.             mul = ((mul % mod) * (abs(parent[i]) % mod)) % mod;
  46.         }
  47.     }
  48.  
  49.    cout << mul << endl;
  50.  
  51.     return 0;
  52. }
RAW Paste Data