Advertisement
limimage

Untitled

May 26th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<set<int> > rg;
  5. vector<int> dependencies;
  6. vector<vector<int> > graph;
  7. int n;
  8. void getDependence(int f, int & ans) {
  9.   ans |= (1<<f);
  10.   for(int v : rg[f]) {
  11.     if((ans & (1<<v)) == 0)
  12.       getDependence(v, ans);
  13.     ans |= (1<<v);
  14.   }
  15. }
  16.  
  17. int checkBit(int val, int bit) {
  18.   return (val>>bit)&1;
  19. }
  20. vector<vector<int> > answer;
  21.  
  22. int getNextBit(int mask, int nxt) {
  23.   int answer = 0;
  24.   nxt -= mask;
  25.   while(nxt) {
  26.     answer++;
  27.     nxt /= 2;
  28.   }
  29.   return answer;
  30. }
  31.  
  32. void buildAnswer(int mask, vector<int> v) {
  33.   if(mask == (1<<n) - 1) {
  34.     answer.push_back(v);
  35.     return;
  36.   }
  37.   for(int nextMask : graph[mask]) {
  38.     vector<int> nextVector = v;
  39.     nextVector.push_back(getNextBit(mask, nextMask));
  40.     buildAnswer(nextMask, nextVector);
  41.   }
  42. }
  43.  
  44. struct Answer {
  45.   vector<int> v;
  46.   Answer(vector<int> v) {
  47.     this->v = v;
  48.   }
  49.   bool operator < (const Answer & o) {
  50.     for(int i = 0; i < (int)o.v.size();i++) {
  51.       if(v[i] != o.v[i]) {
  52.         return v[i] < o.v[i];
  53.       }
  54.     }
  55.   }
  56. };
  57.  
  58. int main() {
  59.   ios_base::sync_with_stdio(false);
  60.   cin.tie(nullptr);
  61.   cin>>n;
  62.   rg.resize(n);
  63.   dependencies.resize(n, 0);
  64.   int m;
  65.   cin>>m;
  66.   for(int i=0; i<m; i++) {
  67.     int f,t;
  68.     cin>>f>>t;
  69.     if(f == t) {
  70.       cout << "no";
  71.       return 0;
  72.     }
  73.     rg[t - 1].insert(f - 1);
  74.   }
  75.   for(int i=0; i<n; i++) {
  76.     getDependence(i, dependencies[i]);
  77.   }
  78.  
  79.   set<int> values;
  80.   for(int val : dependencies) {
  81.     if(values.find(val) != values.end()) {
  82.       cout<<"no";
  83.       return 0;
  84.     }
  85.     values.insert(val);
  86.   }
  87.  
  88.  
  89.   graph.resize(1<<n);
  90.  
  91.   for(int mask = 0; mask < (1<<n); mask++) {
  92.     for(int bit = 0; bit < n; bit++) {
  93.       if(!checkBit(mask, bit)) {
  94.         int nextMask = (mask + (1<<bit));
  95.         if((dependencies[bit] & nextMask) == dependencies[bit]) {
  96.           graph[mask].push_back(nextMask);
  97.         }
  98.       }
  99.     }
  100.   }
  101.  
  102.   buildAnswer(0, {});
  103.  
  104.   cout<<answer.size()<<endl;
  105.   vector<Answer> vect;
  106.   for(vector<int> & v : answer) {
  107.     vect.push_back(v);
  108.   }
  109.  
  110.   sort(vect.begin(), vect.end());
  111.   for(auto a : vect) {
  112.     for(int val : a.v) {
  113.       cout << val << " ";
  114.     }
  115.     cout << "\n";
  116.   }
  117.  
  118.   return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement