Kosaraju算法，然後bitset優化

 

主要是學習一下自寫bitset的姿勢

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,l,r) for(int i=l;i<=r;i++)#define dow(i,l,r) for(int i=r;i>=l;i--)#define rep0(i,r) for(int i=0;i
          
           =0;i=e[i].next)#define maxn 550#define maxm 100100#define LL long longusing namespace std;int tot,p[maxn],n,m,kk;char s[maxn];struct Bitset{    unsigned int v[8];    void reset()  //clear    {        memset(v,0,sizeof(v));    }    void set(int x) //set v[x]=1    {        v[x>>5]|=1u<<(x&31);    }    void flip(int x) // rev    {        v[x>>5]^=1u<<(x&31);    }    bool ask(int x)  // is == 1?    {        return v[x>>5]>>(x&31)&1;    }}vis,g[maxn],rg[maxn];//vis[] =1 not vis,=0 vis//g[i][j] =1 exist i->j,=0 not exist//rg[i][j] =1 exist j->i,=0 not exist;void add(int j,int k){    g[j].flip(k);    rg[k].flip(j);}int nlz(unsigned int x){   int n;   n = 1;   if ((x >> 16) == 0) {n = n +16; x = x <<16;}   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}   n = n - (x >> 31);   return 31-n;}void dfs0(int x){    vis.flip(x);    rep0(i,8) {        unsigned int now=vis.v[i]&g[x].v[i];        while (now) {            dfs0(i<<5|nlz(now));            now=vis.v[i]&g[x].v[i];        }    }    p[++tot]=x;}void dfs1(int x){    vis.flip(x);    ++tot;    rep0(i,8) {        unsigned int now=vis.v[i]&rg[x].v[i];        while (now) {            dfs1(i<<5|nlz(now));            now=vis.v[i]&rg[x].v[i];        }    }}int calc(){    vis.reset();    rep0(i,n) vis.set(i);    tot=0;    rep0(i,n)        if (vis.ask(i)) dfs0(i);    rep0(i,n) vis.set(i);    int ans=0;    dow(i,1,n)        if (vis.ask(p[i])) {            tot=0;            dfs1(p[i]);            ans+=tot*(tot-1)/2;        }    return ans;}int main(){    int tt;    scanf("%d",&tt);    while (tt--) {        scanf("%d %d",&n,&m);        rep0(i,n) {            g[i].reset();            rg[i].reset();        }        rep0(i,n) {            scanf("%s",s);            rep0(j,n)                if (s[j]=='1') add(i,j);        }        while (m--) {            scanf("%d",&kk);            while (kk--) {                int j,k;                scanf("%d %d",&j,&k);                add(j-1,k-1);            }            printf("%d\n",calc());        }    }    return 0;}
          
         
        
       
      

 

另外是一個總結

Bitset头文件：#include
      
       bitset<32> bits;  b.any() b中是否存在置为1的二进制位？b.none() b中不存在置为1的二进制位吗？b.count() b中置为1的二进制位的个数b.size() b中二进制位数的个数b[pos] 访问b中在pos处二进制位b.test(pos) b中在pos处的二进制位置为1么？b.set() 把b中所有二进制位都置为1b.set(pos) 把b中在pos处的二进制位置为1b.reset( ) 把b中所有二进制位都置为0b.reset( pos ) 把b中在pos处的二进制位置置为0b.flip( ) 把b中所有二进制位逐位取反b.flip( pos ) 把b中在pos处的二进制位取反b.to_ulong( ) 把b中同样的二进制位返回一个unsignedint __builtin_ffs (unsigned x) 返回x中最后一个1是从右往左第几位int __builtin_popcount (unsigned x) 返回x中1的个数int __builtin_ctz (unsigned x) 返回x末尾0的个数(x等于0时未定义)int __builtin_clz (unsigned x) 返回x中前导0的个数(x等于0时未定义)int __builtin_parity (unsigned x) 返回x中1的奇偶性