解题思路

考试题，想到传递闭包了，写了个O(n^3)的，T了7个点。。。后来看题解是tm的bitset优化？？？以前好像没听过诶（我太菜了），其实也不难，时间复杂度O(n^3/32)

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN = 1005;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int n,m,ans;bitset
           
             a[MAXN];int main(){// freopen("rank.in","r",stdin);// freopen("rank.out","w",stdout); n=rd(),m=rd();int x,y; while(m--){ x=rd(),y=rd(); a[x][y]=1; } for(int k=1;k<=n;k++) for(register int i=1;i<=n;i++) if(a[i][k]) a[i]|=a[k]; for(int i=1;i<=n;i++){ bool flag=1; for(register int j=1;j<=n;j++) if(i!=j) if(!a[i][j] && !a[j][i]) {flag=0;break;} if(flag) ans++; } printf("%d",ans); return 0;}