Advertisement
madhukeshk3

Total Number Of Topological Sort

Jul 30th, 2020
1,918
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pfin(a) printf("%d\n",a);
  5. #define pfln(a) printf("%lld\n",a);
  6. #define pfis(a) printf("%d ",a);
  7. #define pfls(a) printf("%lld ",a);
  8. #define sfi(a) scanf("%d",&a);
  9. #define sfl(a) scanf("%lld",&a);
  10. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define pb(a) push_back(a);
  13. #define mp(a,b) make_pair(a,b)
  14. #define ll long long
  15. #define F first
  16. #define S second
  17. #define vi vector<int>
  18. #define vc vector<char>
  19.  
  20. vi g[21];
  21.  
  22. int n;
  23. ll cnt=0;
  24. int all_visited;
  25.  
  26. ll dp[(1<<21)];
  27.  
  28. ll rec(int mask,vi ind)
  29. {
  30.     if(dp[mask]!=-1)
  31.         return dp[mask];
  32.     if(mask==all_visited)
  33.         return dp[mask]=1;
  34.  
  35.     ll ans=0;
  36.  
  37.     f(i,0,n)
  38.     {
  39.         if((ind[i]==0) && ((mask&(1<<i))==0))
  40.         {
  41.             vi temp(ind);
  42.  
  43.             f(j,0,g[i].size())
  44.             {
  45.                 int v=g[i][j];
  46.                 temp[v]--;
  47.             }
  48.             ans=ans+rec((mask|(1<<i)),temp);
  49.         }
  50.     }
  51.  
  52.     return dp[mask]=ans;
  53. }
  54.  
  55. int main()
  56. {
  57.     int m;
  58.     sfi(n)
  59.     sfi(m)
  60.  
  61.     vi ind(n);
  62.  
  63.     memset(dp,-1,sizeof(dp));
  64.  
  65.     all_visited=(1<<n)-1;
  66.  
  67.     f(i,0,n)
  68.         ind[i]=0;
  69.  
  70.     while(m--)
  71.     {
  72.         int u,v;
  73.         sfi(u)
  74.         sfi(v)
  75.         u--;
  76.         v--;
  77.         g[u].pb(v)
  78.         ind[v]++;
  79.     }
  80.    
  81.  
  82.     ll ans=rec(0,ind);
  83.  
  84.     pfln(ans);
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement