HDU 6072 Logical Chain（Kosaraju+bitset）

http://acm.hdu.edu.cn/showproblem.php?pid=6072

题意：

给你$n*n$的矩阵，每次修改k条边，让你计算其中能相互到达的点对有多少。

思路：

其实就是求强连通分量，如果一个强连通分量里有n个点，那么这里面的点对就有$n*(n-1)/2$。用Kosaraju计算即可，但是这样是会超时的，还需要用bitset来优化。

__builtin_函数中处理二进制位的函数：

int __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的奇偶性

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 using namespace std;
 12 typedef long long ll;
 13 const int INF = 0x3f3f3f3f;
 14 const int maxn=250+5;
 15 
 16 int n, m;
 17 int num;
 18 char s[maxn];
 19 
 20 struct Bitset//用unsigned数组实现bitset，为了使用__builtin_ctz()
 21 {
 22     unsigned v[8];//8个unsigned表示8*32=256位
 23 
 24     void reset()//清零
 25     {
 26         for(int i=0;i<8;++i) v[i]=0;
 27     }
 28     void set(int x)//把某一位设为1
 29     {
 30         v[x>>5]|=1u<<(x&31);
 31     }
 32     void flip(int x)//翻转某一位
 33     {
 34         v[x>>5]^=1u<<(x&31);
 35     }
 36     bool test(int x)//返回某一位是否为1
 37     {
 38         return v[x>>5]>>(x&31)&1;
 39     }
 40 }vis, G[maxn], rG[maxn];
 41 
 42 vector<int> S;
 43 
 44 void dfs1(int u)
 45 {
 46     vis.flip(u);
 47     for(int i=0;i<8;i++)
 48     {
 49         while(true)
 50         {
 51             unsigned tmp=vis.v[i]&G[u].v[i];  //tmp就计算出了可以访问的点
 52             if(!tmp)  break;
 53             dfs1(i<<5|__builtin_ctz(tmp));  //计算出tmp末尾有多少0，有多少0就代表了它是第几位，这儿的话一个点一个点的来
 54         }
 55     }
 56     S.push_back(u);
 57 }
 58 
 59 void dfs2(int u)
 60 {
 61     vis.flip(u);
 62     ++num;
 63     for(int i=0;i<8;i++)
 64     {
 65         while(true)
 66         {
 67             unsigned tmp=vis.v[i]&rG[u].v[i];
 68             if(!tmp)  break;
 69             dfs2(i<<5|__builtin_ctz(tmp));
 70         }
 71     }
 72 }
 73 
 74 void Kosaraju()
 75 {
 76     S.clear();
 77     int ans=0;
 78     for(int i=0;i<n;i++)  vis.set(i);
 79     for(int i=0;i<n;i++)  if(vis.test(i))  dfs1(i);
 80     for(int i=0;i<n;i++)  vis.set(i);
 81     for(int i=n-1;i>=0;i--)
 82     {
 83         if(vis.test(S[i]))
 84         {
 85             num=0;
 86             dfs2(S[i]);
 87             ans+=num*(num-1)/2;
 88         }
 89     }
 90     printf("%d
",ans);
 91 }
 92 
 93 
 94 int main()
 95 {
 96     //freopen("in.txt","r",stdin);
 97     int T;
 98     scanf("%d",&T);
 99     while(T--)
100     {
101         scanf("%d%d",&n,&m);
102         for(int i=0;i<n;i++) G[i].reset(),rG[i].reset();
103         for(int i=0;i<n;i++)
104         {
105             scanf("%s",s);
106             for(int j=0;j<n;j++)  if(s[j]=='1')
107             {
108                 G[i].flip(j);
109                 rG[j].flip(i);
110             }
111         }
112         while(m--)
113         {
114             int t; scanf("%d",&t);
115             while(t--)
116             {
117                 int u,v;
118                 scanf("%d%d",&u,&v);
119                 G[u-1].flip(v-1);
120                 rG[v-1].flip(u-1);
121             }
122             Kosaraju();
123         }
124     }
125     return 0;
126 }