Code Book

This is my algorithm codebook. Here I keep all my algorithm and data structure codes.

Contents

Contest Template

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define VI               vector <int>
#define MOD              1000000007
#define fast_cin         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define UNIQUE(v)        (v).erase(unique((v).begin(),(v).end()),(v).end())
#define POPCOUNT         __builtin_popcountll
#define RIGHTMOST        __builtin_ctzll
#define LEFTMOST(x)      (63-__builtin_clzll((x)))
#define NUMDIGIT(x,y)    (((vlong)(log10((x))/log10((y))))+1)
#define NORM(x)          if(x>=mod) x-=mod;if(x<0) x+=mod;
#define ODD(x)           (((x)&1)==0?(0):(1))
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))
#define D(x)            cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define DD(x,y)          cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define DDD(x,y,z)       cerr << __LINE__ << ": " << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << '\n'
#define DBG              cerr << __LINE__ << ": Hi" << '\n'

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


int main() {
//#ifndef ONLINE_JUDGE
////    freopen("in.txt","r",stdin);
////      freopen("out.txt","w",stdout);
//#endif

    return 0;
}

Sieve

#define mx 50006
vector<int>prime;

bool vis[mx];

void sieve() {
    int x=sqrt((int)mx);
    for(int i=3; i<=x; i+=2) {
        if(vis[i]==0) {
            for(int j=i*i; j<mx; j+=2*i)
                vis[j]=1;
        }
    }
    prime.pb(2);
    for(int i=3; i<mx; i+=2)
        if(vis[i]==0)
            prime.pb(i);
}

Bitwise Sieve

#define M 40000000
int marked[M/64 + 2];
vector<int>prime;

#define on(x) (marked[x/64] & (1<<((x%64)/2)))
#define mark(x) marked[x/64] |= (1<<((x%64)/2))

bool isPrime(int num) {
    return num > 1 && (num == 2 || ((num & 1) && !on(num)));
}

void sieve(int n) {
    for (int i = 3; i * i < n; i += 2) {
        if (!on(i)) {
            for (int j = i * i; j <= n; j += i + i) {
                mark(j);
            }
        }
    }
    prime.push_back(2);
    for(int i=3; i<M; i+=2) {
        if(isPrime(i))
            prime.pb(i);
    }
}

Segmented Sieve

#define mx 100005
vector<int>prime;

bool vis[mx];

void sieve() {
    int x=sqrt((int)mx);
    for(int i=3; i<=x; i+=2) {
        if(vis[i]==0) {
            for(int j=i*i; j<mx; j+=2*i)
                vis[j]=1;
        }
    }
    prime.pb(2);
    for(int i=3; i<mx; i+=2)
        if(vis[i]==0)
            prime.pb(i);
}


int segmented_sieve(int a, int b) {
    memset(vis,0,sizeof vis);
    if(b<2) return 0;
    if(a<2) a=2;
    int xx=sqrt((double)b)+1;
    for(ll i=0; i<SZ(prime) && prime[i]<=xx; i++) {
        ll j=(a/prime[i]);
        if(a%prime[i]!=0) j++;
        j*=prime[i];
        if(j==prime[i]) j+=prime[i];
        for(; j<=b; j+=prime[i])
            vis[j-a]=1;
    }
    int cnt=0;
    for(ll i=a; i<=b; i++)
        if(vis[i-a]==0) cnt++;
    return cnt;
}

Number of Divisor

long long NOD(long long n) {
    int root=sqrt(n);
    long long ret=1;
    for(int i=0; i<prime.size() && prime[i]<=root; i++) {
        if(n%prime[i]==0) {
            int cnt=1;
            while(n%prime[i]==0) {
                cnt++;
                n/=prime[i];
            }
            ret*=cnt;
            root=sqrt(n);
        }
    }
    if(n>1)
        ret*=2;
    return ret;
}

Euler Totient

long long euler_totient(long long n) {
    int root=sqrt(n);
    long long ret=n;
    for(int i=0; i<prime.size() && prime[i]<=root; i++) {
        if(n%prime[i]==0) {
            while(n%prime[i]==0)
                n/=prime[i];
            root=sqrt(n);
            ret-=(ret/prime[i]);
        }
    }
    if(n>1) {
        ret-=(ret/n);
    }
    return ret;
}

Euler Totient Precompute

#define mx 100005
int phi[mx];

void euler_totient() {
    for(int i=0; i<mx; i++) phi[i]=i;
    for(int i=2; i<mx; i++) {
        if(phi[i]==i) {
            for(int j=i; j<mx; j+=i)
                phi[j]-=(phi[j]/i);
        }
    }
}

Extended Euclid

long long ext_gcd (long long A, long long B, long long &X, long long &Y) {
    long long x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1, y2 = 0;
    x1 = 0, y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    } X
        = x2;
    Y = y2;
    return r2;
}

Big Mod

inline long long bigmod (long long a, long long p, long long m) {
    long long res = 1 % m, x = a % m;
    while ( p ) {
        if ( p & 1 ) res = ( res * x ) % m;
        x = ( x * x ) % m;
        p >>= 1;
    }
    return res;
}

Mod Inverse

Using Extended Euclidian Algorithm

inline long long modInv (long long a, long long m) {
    long long x, y;
    ext_gcd(a, m, x, y);
    x %= m;
    if (x < 0) x += m;
    return x;
}

Using Big Mod Algorithm

long long modInv = bigmod(a, m-2, m);

Linear Diophantine Equation

bool linearDiophantine ( long long A, long long B, long long C, long long &x, long long &y ) {
    int g = gcd ( A, B );
    if ( C % g != 0 ) return false; //No Solution
    int a = A / g, b = B / g, c = C / g;
    if ( g < 0 ) { //Make Sure gcd(a,b) = 1
        a *= -1;
        b *= -1;
        c *= -1;
    }
    ext_gcd( a, b, x, y ); //Solve ax + by = 1
    x *= c;
    y *= c; //ax + by = c
    return true; //Solution Exists
//more solution {x+k*(b/g), y-k*(a/g)}
}

Chinese Remainder Theorem

long long CRT_weak(vector<long long>A, vector<long long>B) {
    long long X=0;
    long long N=1;
    long long y,z;
    for(int i=0; i<B.size(); i++)
        N*=B[i];
    for(int i=0; i<A.size(); i++) {
        y=N/B[i];
        z=modInv(y,B[i]);
        X+=(A[i]*y*z);
        X%=N;
    }
    return (X+N)%N;
}

Mobius Function

int mu[mx];

void mobius() {
    for(int i=1; i<mx; i++) mu[i]=1;
    int root=sqrt((int)mx);
    for(int i=0; i<prime.size() && prime[i]<=root; i++) {
        int x=prime[i];
        x=x*x;
        for(int j=x; j<mx; j+=x)
            mu[j]=0;
    }
    for(int i=0; i<prime.size(); i++) {
        int x=prime[i];
        for(int j=x; j<mx; j+=x)
            mu[j]*=-1;
    }
}

Breadth-first search (BFS)

#define mx 100005

vector<int> g[mx],cost[mx]; //Graph adjacency list
int dis[mx], par[mx];

int bfs(int src, int dst){
    memset(dis,-1,sizeof dis);
    dis[src]=0;
    par[src]=-1; //Required for path print
    queue<int>Q;
    Q.push(src);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        if(u==dst) return dis[dst];
        for(int v:g[u]){
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                par[v]=u;
                Q.push(v);
            }
        }
    }
}

//Run bfs() before executing this function
void path_print(int src, int dst){
    vector<int>path;
    int u = dst;
    while(u!=-1){
        path.push_back(u);
        u=par[u];
    }
    reverse(path.begin(),path.end());
    for(int u:path){
        cout<<u<<" ";
    }
    cout<<endl;
}

0-1 BFS

#define mx 100005

vector<int> g[mx],cost[mx]; //Graph adjacency list
int dis[mx];

int bfs(int src, int dst){
    fill(dis,dis+mx,1e9);
    dis[src]=0;
    deque<int>Q;
    Q.push_back(src);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop_front();
        if(u==dst) return dis[dst];
        for(int i=0;i<g[u].size();i++){
            int c = cost[u][i];
            int v = g[u][i];
            if(dis[v] > dis[u]+c){
                dis[v]=dis[u]+c;
                if(c==0) // Push front if cost is 0
                    Q.push_front(v);
                else // Push back if cost is 1
                    Q.push_back(v);
            }
        }
    }
}

Dijkstra

#define mx 100005

vector<int> g[mx],cost[mx]; //Graph adjacency list
int dis[mx];

int Dijkstra(int src, int dst){
    fill(dis,dis+mx,1e9);
    dis[src]=0;
    priority_queue<pair<long long,int> >Q; // first of pair is cost and second is node
    Q.push(make_pair(-0,src));
    while(!Q.empty()){
        int u = Q.top().second;
        Q.pop();
        if(u==dst) return dis[dst];
        for(int i=0;i<g[u].size();i++){
            int c = cost[u][i];
            int v = g[u][i];
            if(dis[v] > dis[u]+c){
                dis[v]=dis[u]+c;
                Q.push(make_pair(-dis[v],v)); // this negation is required for priority_queue order
            }
        }
    }
}

Shortest Path Faster Algorithm (SPFA)

#define mx 100005

vector<int> g[mx],cost[mx]; //Graph adjacency list
int dis[mx], inQueue[mx], cntPushQueue[mx];
int NODE;

int SPFA(int src, int dst) {
    fill(dis,dis+mx,1e9);
    memset(inQueue,0,sizeof inQueue);
    memset(cntPushQueue,0,sizeof cntPushQueue);

    dis[src]=0;
    inQueue[src]=1; // inQueue[u] indicate that whether u is currently inside of Queue or not.
    cntPushQueue[src]=1;

    queue<int>Q;
    Q.push(src);
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        inQueue[u]=0;
        if(cntPushQueue[u]>=NODE){ //Negative cycle detected
            return -1;
        }
        for(int i=0; i<g[u].size(); i++) {
            int c = cost[u][i];
            int v = g[u][i];
            if(dis[v] > dis[u]+c) {
                dis[v]=dis[u]+c;
                if(inQueue[v]==0) {
                    Q.push(v);
                    inQueue[v]=1;
                    cntPushQueue[v]++;
                }
            }
        }
    }
    return dis[dst];
}

Floyd–Warshall

// let p be a 2D parent matrix, where p[i][j] is the last vertex before j
// on a shortest path from i to j, i.e. i -> ... -> p[i][j] -> j
init_path_print() {
    for (int i = 0; i < NODE; i++)
        for (int j = 0; j < NODE; j++)
            p[i][j] = i; // initialize the parent matrix
}

// precondition: AdjMat[i][j] contains the weight of edge (i, j)
// or INF (1B) if there is no such edge
// AdjMat is a 32-bit signed integer array
void floyd_warshall() {
    for (int k = 0; k < NODE; k++) {// remember that loop order is k->i->j
        for (int i = 0; i < NODE; i++) {
            for (int j = 0; j < NODE; j++) {
                AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j]);
                p[i][j] = p[k][j]; // update the parent matrix for path print
            }
        }
    }
}

// when we need to print the shortest paths, we can call the method below:
void printPath(int i, int j) {
    if (i != j) printPath(i, p[i][j]);
    printf(" %d", j);
}

Depth-first search (DFS)

#define mx 100005

vector<int> g[mx]; //Graph adjacency list
pair<int,int> dfs_time[mx];
bool visited[mx];
int Time = 0;

void dfs(int u){
    visited[u]=1;
    dfs_time[u].first = Time++;
    for(int v:g[u]){
        if(visited[v]) continue;
        dfs(v);
    }
    dfs_time[u].second = Time++;
}

Articulation Point

/// Articulation Point
/// Call findAP() to find the articulation points

const int NODE = 2e5; /// Maximum no of node (1 based indexing)

int disc[NODE], low[NODE], isap[NODE], vis[NODE], par[NODE];
vector<int> G[NODE];
/// isap[u] = 1 if u is an articulation point.

struct AP{
    int Time = 0;

    AP():Time(0) {}
    void clear(){
        for(int u = 0;u<NODE;u++){
            G[u].clear();
            disc[u] = low[u] = isap[u] = vis[u] = 0;
            par[u] = -1;
        }
    }
    void tarjan(int u) {
        disc[u] = low[u] = ++Time;
        vis[u] = 1;
        int ch = 0; /// No of unvisited child
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (vis[v] == 0) {
                par[v] = u;
                ch++;
                tarjan(v);
                low[u] = min(low[v], low[u]);
                if (par[u] == -1 && ch > 1) isap[u] = 1; /// Found an AP
                if (par[u] != -1 && low[v] >= disc[u]) { /// Found an AP
                    isap[u] = 1;
                }
            } else if (v != par[u]) {
                low[u] = min(disc[v], low[u]);
            }
        }
    }
    void findAP(int N) {
        for (int i = 1; i <= N; i++) {
            if (vis[i] == 0) {
                tarjan(i);
            }
        }
    }
}ap;

Articulation Bridge

/// Articulation Bridge
/// Call findBridge() to find the articulation bridge

const int NODE = 2e5; /// Maximum no of node (1 based indexing)

vector<int> G[NODE];
int disc[NODE], low[NODE], vis[NODE], par[NODE];

struct Bridge{
    int Time = 0;

    Bridge():Time(0) {}
    void clear(){
        for(int u = 0;u<NODE;u++){
            G[u].clear();
            disc[u] = low[u]  = vis[u] = 0;
            par[u] = -1;
        }
    }
    void tarjan(int u) {
        disc[u] = low[u] = ++Time;
        vis[u] = 1;

        for (int i = 0; i < (int) G[u].size(); i++) {
            int v = G[u][i];
            if (vis[v] == 0) {
                par[v] = u;
                tarjan(v);
                low[u] = min(low[v], low[u]);
                if (low[v] > disc[u]) { /// u-v is a bridge
                    /// Do whatever you like now with it...
                }
            } else if(v != par[u]) {
                low[u] = min(disc[v], low[u]);
            }
        }
    }
    void findBridge(int N) {
        for (int i = 1; i <= N; i++) {
            if (vis[i] == 0) {
                tarjan(i);
            }
        }
    }
}bridge;

Biconnected Component (BCC)

/// Biconnected Components
/// Call findBCC() to find the bcc components
/// BCC.clear() clear all the graph so call BCC.clear before graph input

const int NODE = 2e5; /// Maximum no of node (1 based indexing)

int disc[NODE], low[NODE], vis[NODE];
vector <int> G[NODE];
stack< pii > st;

struct BCC
{
    int Time = 0;

    BCC():Time(0) {}
    void clear()
    {
        for(int u = 0; u<NODE; u++)
        {
            G[u].clear();
            disc[u] = low[u]  = vis[u] = 0;
        }
        while(!st.empty()) st.pop();
    }
    void tarjan(int u, int par)
    {
        vis[u] = 1;
        disc[u] = low[u] = ++Time;
        for(int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if(v == par) continue;
            if(!vis[v])
            {
                st.push(MP(u, v));
                tarjan(v, u);
                if(low[v] >= disc[u])   /// Found a new BCC x, modify here with your needs
                {
                    pii tmp = MP(u, v), e;
                    do
                    {
                        e = st.top(); /// e is an edge of BCC x
                        st.pop();
                    }
                    while(e != tmp);
                }
                low[u] = min(low[u], low[v]);
            }
            else if(disc[v] < disc[u])
            {
                st.push(MP(u, v));
                low[u] = min(low[u], disc[v]);
            }
        }
    }
    void findBCC(int N)
    {
        for(int i = 0; i <N; i++)
        {
            if(disc[i] == 0)
            {
                tarjan(i, -1);
            }
        }
    }
} bcc;

Block-Cut Tree

/**
    1. Take input the graph in g[].
    2. Call find_BCC() to determine biconnected components which are stored in BCC.
    3. Call build_BCTree() to get block cut tree in tree[].
    4. Always remember to clear BCC and AP before buld tree.  
*/

#define mx 10004

vector<int>g[mx];
int disc[mx],low[mx],dfs_time;
bool vis[mx],isAP[mx];
stack<int>st;

vector<vector<int> > BCC; ///Store Biconnected components.
vector<int> AP; ///Store articulation points.

///Return number of node in current component
int find_BCC(int u, int p) 
{
    vis[u]=1;
    disc[u]=low[u]=++dfs_time;
    st.push(u);
    int child=1;
    for(int v:g[u])
    {
        if(v==p) continue;
        if(vis[v]==0)
        {
            child+=find_BCC(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=disc[u])
            {
                isAP[u]=(disc[u]>1 || disc[v]>2);
                if(isAP[u]) AP.pb(u);
                BCC.pb({});
//                cout<<"--------------------"<<endl;
                while(true)
                {
                    int cur=st.top();
//                    cout<<cur<<endl;
                    BCC.back().pb(cur);
                    st.pop();
                    if(cur==v)break;
                }
                BCC.back().pb(u);
//                cout<<u<<endl;
            }
        }
        else
        {
            low[u]=min(low[u],disc[v]);
        }
    }
    if(u==p)
    {
        if(SZ(BCC)==0)
        {
            BCC.pb({});
            BCC.back().pb(u);
        }
    }
    return child;
}

///Block cut tree can hold 2*n node where all vertex are cut vertex
vector<int>tree[2*mx];
int tree_node_cnt;
int node_mark[mx];
int elem_cnt[2*mx];

void build_BCTree()
{

    ///Clearing the tree
    for(int i=0; i<=tree_node_cnt+2; i++)
    {
        tree[i].clear();
        elem_cnt[i]=0;
    }
    tree_node_cnt=0;

    for(int u:AP)
    {
        node_mark[u]=++tree_node_cnt; ///Creating node for every AP.
        elem_cnt[tree_node_cnt]=1;
    }

    for(int i=0; i<SZ(BCC); i++)
    {
        tree_node_cnt++; /// Creating block node.
        elem_cnt[tree_node_cnt]=SZ(BCC[i]);
        for(int u:BCC[i])
        {
            if(!isAP[u])
                node_mark[u]=tree_node_cnt;
            else        ///Adding edge between a block and AP node.
            {
                tree[tree_node_cnt].pb(node_mark[u]);
                tree[node_mark[u]].pb(tree_node_cnt);
//                elem_cnt[tree_node_cnt]--;
            }
        }
    }
}

void allclear(int n)
{
    for(int i=0; i<=n; i++)
    {
        g[i].clear();
        vis[i]=0;
        isAP[i]=0;
    }
    while(!st.empty()) st.pop();
    dfs_time=0;
}

Strongly Connected Components (SCC) – Tarjan

#define mx 100005

int disc[mx],low[mx],dfsnum,scc_cnt;
bool vis[mx];
vector<int>g[mx],scc;

void allclear()
{
    for(int i=0;i<mx;i++)
    {
        disc[i]=low[i]=vis[i]=0;
        g[i].clear();
    }
    scc.clear();
    dfsnum=0;
    scc_cnt=0;
}

void Tarjan_SCC(int u)
{
    disc[u]=low[u]=++dfsnum;
    vis[u]=1;
    scc.pb(u);
    for(int i=0;i<SZ(g[u]);i++)
    {
        int v=g[u][i];
        if(disc[v]==0)
            Tarjan_SCC(v);
        if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    if(low[u]==disc[u]) // SCC found
    {
        scc_cnt++;
        while(1) // these are the SCC elements
        {
            int v=scc.back();
            scc.pop_back();
            vis[v]=0;
            if(v==u)
                break;
        }
    }
}

2 – SAT

///Always remember to call allclear() function before execution

const int NODE = 205; /// Maximum no of node (0 based indexing)

vector<int>g[NODE];

int getNode(int x) { ///Convert a choice to node
    int p=abs(x);
    p=(p-1)*2;
    if(x<0) p^=1;
    return p;
}

int getNodeVal(int x) { ///Convert a node to choice
    int p=1;
    if(x&1) {
        p=-1;
        x-=1;
    }
    x/=2;
    x++;
    p*=x;
    return p;
}


///Always pass getNode() value to the folloing function
///For example if we want to mustTrue 5 then the call will be mustTrue(getNode(5))

void mustTrue (int a) { /// A is True
    g[a^1].push_back(a);
}

void xorClause(int a, int b) { /// A ^ B clause
    //!a->b !b->a a->!b b->!a
    g[a^1].push_back(b);
    g[a].push_back(b^1);
    g[b^1].push_back (a);
    g[b].push_back (a^1);
}

void orClause (int a, int b) { /// A || B clause
    //!a->b !b->a
    g[a^1].push_back ( b );
    g[b^1].push_back ( a );
}

void andClause (int a, int b) { /// A && B clause
    mustTrue(a);
    mustTrue(b);
}

/// Out of all possible option, at most one is true
void atMostOneClause ( int a[], int n, int flag) {
    if ( flag == 0 ) { /// At most one can be false
        for(int i = 0; i<n; i++) {
            a[i] = a[i] ^ 1;
        }
    }
    for(int i = 0; i<n; i++) {
        for(int j = i+1; j<n; j++) {
            orClause( a[i] ^ 1, a[j] ^ 1 ); /// !a || !b both being true not allowed
        }
    }
}

///SCC variables
int disc[NODE],low[NODE],Time, scc_count;
int component[NODE];
stack<int>scc;
bool vis[NODE];

///2-SAT variables
deque<int>sat;
int isSAT[NODE];

void allclear() {
    for(int i=0; i<NODE; i++) {
        g[i].clear();
        disc[i]=0;
        low[i]=0;
        component[i]=0;
        isSAT[i]=-1;
    }

    scc_count=0;
    Time=0;
    while(!scc.empty())
        scc.pop();
    sat.clear();
}

void tarjan_SCC(int u) {
    disc[u]=low[u]=++Time;
    scc.push(u);
//    vis[u]=1;
    for(int i=0; i<g[u].size(); i++) {
        int v=g[u][i];
        if(disc[v]==0)
            tarjan_SCC(v);
        if(disc[v]!=-1)
            low[u]=min(low[u],low[v]);
    }
    if(low[u]==disc[u]) {
        scc_count++;
        int v;
        do {
            v=scc.top();
            scc.pop();
            sat.push_back(v);
            component[v]=scc_count;
            disc[v]=-1;
        } while(v!=u);
    }
}

bool checkSAT(int n) {
    while(!sat.empty()) { ///Assigning valid values to candidates
        int x=sat.front();
        sat.pop_front();
        if(isSAT[x]==-1) {
            isSAT[x]=1;
            x=getNode(-getNodeVal(x)); ///Getting opposite value
            isSAT[x]=0;
        }
    }

    ///Checking whether satisfiability is possible or not
    bool check=1;
    for(int i=1; i<=n && check; i++) {
        check=(component[getNode(i)]!=component[getNode(-i)]);
    }
    return check;
}
4.6 9 votes
Article Rating
Subscribe
Notify of
guest
6 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Ramisa

This is exactly what I was looking for! Thank You!

3
Reply
Partha Proteem Ghose

Nice Jobs

0
Reply
akshay

Can someone please explain Bitwise Sieveor provide a link to online tutorial where I can understand this.
I need this to solve CPRIME in spoj.

thanks!

0
Reply
ritu

Extended gcd :——–
int ext_gcd (

int A,

int B,

int *X,

int *Y )

here input gula bujhi ni… *X , *Y er jonno input ki hobe??

0
Reply
Tanmoy Datta

Here *X and *Y are two pointer variable which holds the result. You have to pass two variables in place of *X and *Y. Then after execution of the function the result will be inside of those variables. For example –

int P,Q,G;
G = ext_gcd(3,5,P,Q)
Now we can write that 3P + 5Q = G

0
Reply
Ahmad Hossain Sajid

Thanks a lot ,bhaiya

0
Reply