P2341 [HAOI2006]受欢迎的牛 暴力

//n方过百万，暴力碾标算
//我相信：暴力出奇迹 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAXN 10005
using namespace std;
int vis[MAXN];
int is_all[MAXN];//是否全部被欢迎:-1不确定，1：全部被欢迎，0：不全部被欢迎 
int sz[MAXN];
int haveans;
vector<int>G[MAXN];
void dfs(int u){
    if (haveans==1){
        return ;
    }
    for (register int i=0;i<sz[u];++i){
        if (!vis[G[u][i]]){
            vis[G[u][i]]=true;
            if (is_all[G[u][i]]==1){//剪枝1：当搜索到一只奶牛，从它出发能到达所有奶牛，则从这只奶牛出发能够到达所有奶牛
                haveans=is_all[G[u][i]];
                return ;
            }
            dfs(G[u][i]);
        }
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for (register int i=0;i<m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        vis[u]=true,vis[v]=true;
        G[v].push_back(u);
    }
    bool flag=false;
    for (register int i=1;i<=n;++i){
        if (vis[i]==0){
            flag=true;
            break;
        }
    }
    if (flag==true){//第二个剪枝，如果有奶牛没有在图中，则答案为0
        printf("0\n");
        return 0;
    }
    for (register int i=1;i<=n;++i){
        sort(G[i].begin(),G[i].end());
        sz[i]=unique(G[i].begin(),G[i].end())-G[i].begin();
    }
    int sum=0;
    memset(is_all,-1,sizeof(is_all));
    for (register int i=1;i<=n;++i){
        if (is_all[i]==0){//无法到达所有奶牛
            continue;
        }
        haveans=-1;
        memset(vis,0,sizeof(vis));
        vis[i]=true;
        dfs(i);
        if (haveans==1){
            is_all[i]=1;
            sum++;
        }
        else if (haveans==-1){
            bool flag=false;
            for (register int j=1;j<=n;++j){
                if (vis[j]==0){
                    flag=true;
                    break;
                }
            }
            if (flag==false){
                is_all[i]=1;
                sum++;
            }
            else {
                for (register int j=1;j<=n;++j){
                    if (vis[j]) is_all[j]=0;
                }
                //这个剪枝很重要，如果此奶牛无法到达所有奶牛，
                //那么此奶牛能够到达的所有奶牛无法到达所有奶牛(有点绕口qwq)
            }
        }
    }
    printf("%d\n",sum);
}