[拓扑序][博弈][重点错误] codeforces 1033C Permutation Game

这个题wa到最后才意识到是dfs刷表的思想本身是错误的，必须按照拓扑序来处理，这两个是不等价的。不等价的原因是dfs可能会多次刷到同一节点而且这个节点的父节点还没有完全确定下来。比如当某个节点只有一个父节点的时候，本来dfs给了他1，也就是必胜态，但是如果某一次之后的刷新把父节点变成了1，那么由于该节点只有一个父节点所以他只能变成0。而原来写的dfs不能解决的就是这样一个问题：对于一个节点来说，是不是所有的父节点都是1或者至少有一个0，因为单纯的dfs可能会求很多遍这个点（如果不这样又没办法更新），如果用拓扑序的话就可以保证在搜到一个点的时候这个点的父节点已经全部搞定了，这也跟拓扑序处理的时候每次只走“一步”有关系。这样的话就可以保证不会有多余的1没有变成0了。

#include

using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const int mod=1e9;

int a[maxn],p[maxn];
vector G[maxn];
int vis[maxn];




priority_queue Q;
int deg[maxn];
//void dfs(int x,int flag)//dfs是错误的做法，会重复递推导致多1
//{
//
//    if(vis[x]==-1)
//    {
//        vis[x]=flag;
//    }
//    else if(flag)
//    {
//        vis[x]=1;
//    }
//    else
//        return ;//prune1
//    //cout<<"motherfucker?"<>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[a[i]]=i;
        //Q.push(node(i,a[i]));
    }
    memset(vis,-1,sizeof(vis));
    for (int i=1; i<=n; ++i)
    {
        for (int j=i+a[i]; j<=n; j+=a[i])
            if (a[j] > a[i])
            {
                G[j].push_back(i), deg[i] ++;
            }

        for (int j=i-a[i]; j>=1; j-=a[i])
            if (a[j] > a[i])
            {
                G[j].push_back(i), deg[i] ++;
            }

    }

    for (int i=1;i<=n;i++)
    {
        if(!deg[i])
        {
            Q.push(i);
            vis[i]=0;
        }

    }

//错误的做法：每次dfs
//    int tp,ta;
//    node tnd;
//    while(!Q.empty())
//    {
//        tp=Q.top();Q.pop();
//        //tp=tnd.p,ta=tnd.a;
//        dfs(tp,0);
//    }


    while (!Q.empty())
    {
        int u = Q.top();Q.pop();
        for (int sz=G[u].size(),i=0; i