hdu 5413 CRB and Roads 位运算优化复杂度

题意：给一个包含n个点m条边的无环单向简单图，然后问有多少条多余边。$(u,v)$是多余边当且仅当$u->v$不经过$(u,v)$这条边。

都说了是无环单向图。因此很容易想到拓扑排序：对于当且点u，如果存在$(u,v)$，v可以由u通过另一条路径到达，那么$(u,v)$这条边就是多余边，但是这样暴力下来复杂度大概是$O(n(n+m))$，然后再乘以一个T($T \le 20$)，就T了。。我的第一个想法是这么做的。然后交上去真的T了。然后又YY到一种做法。能不能保存有哪些点可以到达当前点，维护每一个点的所能到达点的集合，不过这样一来维护的复杂度是$O(n)$，复杂度也没变。。这个是真的没想到能用位运算优化，后来baidu了说用bitset突然就明白了。用位运算可以优化，空间复杂度可以降为$O(\frac{N^2}{32})$，而且每一次维护的复杂度可以从$O(N)$降为$O(\frac{N}{32})$。
这道题的具体做法用到了拓扑序，按照拓扑序来遍历点，对于每一个点u，遍历顺序为拓扑序号高->低，并维护有哪些点可以到达该点，在维护之前先判断是否该点已可到达，如果已可到达就$ans+1$，然后维护并增加该点的u所能到达的点
当然，也可以用STL的bitset来做，这样可以让代码更简短。
代码1：

//author: CHC
//First Edit Time:	2015-08-25 15:45
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=20000 + 10;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int bit[MAXN][MAXN/32+100];
struct Edge {
    int to,next;
    Edge(){}
    Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN*10],e2[MAXN*10];
int head[MAXN],tot,du[MAXN];
int head2[MAXN],tot2;
int n,m;
void init(){
    //memset(head,-1,sizeof(head));
    //memset(head2,-1,sizeof(head2));
    for(int i=1;i<=n;i++)head2[i]=head[i]=-1,du[i]=0;
    tot2=0;
    tot=0;
}
void AddEdge(int u,int v){
    e[tot]=Edge(v,head[u]);
    head[u]=tot++;
}
void AddEdge1(int u,int v){
    e2[tot2]=Edge(v,head2[u]);
    head2[u]=tot2++;
}
int que[MAXN],front,rear;
void _or(int posi,int posj){
    for(int i=0;i<=n/32;i++)bit[posi][i]|=bit[posj][i];
}
void top_bfs(){
    front=rear=0;
    memset(bit,0,sizeof(bit));
    for(int i=1;i<=n;i++){
        bit[i][i/32]=(1<<(i%32));
        if(du[i]==0){
            que[front++]=i;
            --du[i];
        }
    }
    while(front!=rear){
        int u=que[rear++];
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            AddEdge1(v,u);
            if(--du[v]==0)que[front++]=v;
            //bit[u][v/32]|=(1<<(v%32));
        }
    }
}
template <class T>
void Rd(T &tmp){
    char ch;
    while((ch=getchar())&&!isdigit(ch));
    tmp=0;
    do {
        tmp=(tmp<<3)+(tmp<<1)+(ch^48);
    }while((ch=getchar())&&isdigit(ch));
    return ;
}
int main()
{
    int T;
    //scanf("%d",&T);
    Rd(T);
    while(T--){
        //scanf("%d%d",&n,&m);
        Rd(n),Rd(m);
        init();
        for(int i=0,x,y;i<m;i++){
            //scanf("%d%d",&x,&y);
            Rd(x),Rd(y);
            AddEdge(x,y);
            ++du[y];
        }
        top_bfs();
        int ans=0;
        for(int i=0;i<front;i++){
            int u=que[i];
            for(int j=head2[u];~j;j=e2[j].next){
                int v=e2[j].to;
                //printf("%d-->%d\n",u,v);
                if(bit[u][v/32]&(1<<(v%32)))++ans;
                _or(u,v);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

代码2:

//author: CHC
//First Edit Time:	2015-08-25 15:45
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
#include <bitset>
using namespace std;
typedef long long LL;
const int MAXN=20000 + 10;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
//int bit[MAXN][MAXN/32+100];
bitset <MAXN> bit[MAXN];
struct Edge {
    int to,next;
    Edge(){}
    Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN*10],e2[MAXN*10];
int head[MAXN],tot,du[MAXN];
int head2[MAXN],tot2;
int n,m;
void init(){
    //memset(head,-1,sizeof(head));
    //memset(head2,-1,sizeof(head2));
    for(int i=1;i<=n;i++)head2[i]=head[i]=-1,du[i]=0;
    tot2=0;
    tot=0;
}
void AddEdge(int u,int v){
    e[tot]=Edge(v,head[u]);
    head[u]=tot++;
}
void AddEdge1(int u,int v){
    e2[tot2]=Edge(v,head2[u]);
    head2[u]=tot2++;
}
int que[MAXN],front,rear;
//void _or(int posi,int posj){
    //for(int i=0;i<=n/32;i++)bit[posi][i]|=bit[posj][i];
//}
void top_bfs(){
    front=rear=0;
    //memset(bit,0,sizeof(bit));
    for(int i=1;i<=n;i++){
        //bit[i][i/32]=(1<<(i%32));
        bit[i].reset();
        bit[i][i]=1;
        if(du[i]==0){
            que[front++]=i;
            --du[i];
        }
    }
    while(front!=rear){
        int u=que[rear++];
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            AddEdge1(v,u);
            if(--du[v]==0)que[front++]=v;
            //bit[u][v/32]|=(1<<(v%32));
        }
    }
}
template <class T>
void Rd(T &tmp){
    char ch;
    while((ch=getchar())&&!isdigit(ch));
    tmp=0;
    do {
        tmp=(tmp<<3)+(tmp<<1)+(ch^48);
    }while((ch=getchar())&&isdigit(ch));
    return ;
}
int main()
{
    int T;
    //scanf("%d",&T);
    Rd(T);
    while(T--){
        //scanf("%d%d",&n,&m);
        Rd(n),Rd(m);
        init();
        for(int i=0,x,y;i<m;i++){
            //scanf("%d%d",&x,&y);
            Rd(x),Rd(y);
            AddEdge(x,y);
            ++du[y];
        }
        top_bfs();
        int ans=0;
        for(int i=0;i<front;i++){
            int u=que[i];
            for(int j=head2[u];~j;j=e2[j].next){
                int v=e2[j].to;
                //printf("%d-->%d\n",u,v);
                //if(bit[u][v/32]&(1<<(v%32)))++ans;
                if(bit[u][v])++ans;
                bit[u]|=bit[v];
                //_or(u,v);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}