Matrix_code

graph - TwoSAT

Jul 13th, 2017 (edited)
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 101;
  4. // 1 based Indexing.
  5. // call init(n) -> n is number of variable
  6. struct TwoSAT{
  7.     int n,nn;
  8.     vector<int> G[2*N] , R[2*N], top; //G - original graph,R -Reverse graph,top-topological
  9.     int col[2*N],vis[2*N],ok[2*N];   // col- sccNo, ok -> value assignment.
  10.     void init(int n)
  11.     {
  12.         this->n=n;
  13.         this->nn = n+n;
  14.         for(int i=  0; i <= nn; i ++) G[i].clear(), R[i].clear(), col[i] = 0, vis[i] = 0, ok[i] = 0;
  15.         top.clear();
  16.     }
  17.  
  18.     int inv(int no) { return (no <= n) ? no + n: no - n; }
  19.     void add(int u,int v)
  20.     {
  21.         G[u].push_back(v);
  22.         R[v].push_back(u);
  23.     }
  24.     void OR(int u,int v){
  25.         add(inv(u), v);
  26.         add(inv(v), u);
  27.     }
  28.     void AND(int u,int v){
  29.         add(u,v);
  30.         add(v,u);
  31.     }
  32.     void XOR(int u,int v){
  33.         add(inv(v), u);
  34.         add(u, inv(v));
  35.         add(inv(u), v);
  36.         add(v, inv(u));
  37.     }
  38.     void XNOR(int u,int v){
  39.         add(u,v);
  40.         add(v,u);
  41.         add(inv(u), inv(v));
  42.         add(inv(v), inv(u));
  43.     }
  44.     void force_true(int x) {
  45.         add(inv(x),x);
  46.     }
  47.     void force_false(int x) {
  48.         add(x,inv(x));
  49.     }
  50.     void dfs(int u)
  51.     {
  52.         vis[u] = 1;
  53.         for(int i = 0; i < G[u].size(); i ++ ) {
  54.             int v = G[u][i];
  55.             if(vis[v] == 0 ) dfs(v);
  56.         }
  57.         top.push_back(u);
  58.     }
  59.  
  60.     void dfs1(int u,int color)
  61.     {
  62.         col[u] = color;
  63.         if(u <= n) ok[u] = 1;
  64.         else ok[u - n] = 0;
  65.         for(int i = 0 ;i < R[u].size(); i ++ ) {
  66.             if(col[R[u][i]] == 0 )dfs1(R[u][i], color);
  67.         }
  68.     }
  69.     void FindScc()
  70.     {
  71.  
  72.         for(int i = 1; i <= nn ; i ++ ) {
  73.             if(vis[i] == 0 ) dfs(i);
  74.         }
  75.  
  76.         int color = 0;
  77.         reverse(top.begin(), top.end());
  78.         for(auto u: top) {
  79.             if(col[u] == 0) dfs1(u , ++ color);
  80.         }
  81.  
  82.  
  83.     }
  84.     void solve()
  85.     {
  86.         FindScc();
  87.         for(int i=1;i<=n;i++){
  88.             if(col[i] == col[n + i]) {
  89.                 printf("Impossible\n");
  90.                 return;
  91.             }
  92.         }
  93.         vector<int> v;
  94.         for(int i = 1; i <= n; i ++ ) {
  95.             if(ok[i]) v.push_back(i); // All 1'
  96.         }
  97.         cout << v.size() << endl;
  98.         for(auto x: v) printf("%d ",x); puts("");
  99.  
  100.     }
  101. };
Add Comment
Please, Sign In to add comment