【bzoj 十连测】[noip2016第一场]Problem C. Walk（dfs）

在

【题解】【dfs】
【这道题的瓶颈主要在于建图，因为点实在是太太太多了！这样就导致需要枚举的边特别多。如果直接建图跑，果断TLE】
【所以考虑调整一下，使在BFS时需要枚举的边的数量减少一些。类似于以前一个代换的思路】
【类似拆点，将每个点转变为2^20+i并与当前点的权连边，并把2^20内的每个值都与它的子集连边（刚开始把每个点i变为2^20+i就是为了不和这里冲突），边权为零，造出一个用于连每两个满足i&j=j的情况的点的副图】
【dfs预处理第1个点在副图中的边的关系。第2-n点如果能从这些点转移过来，即可以连通。】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
queue<int>que;
int a[2000010],nxt[2000010],p[2000010],point[2000010],tot;
int dis[2000010],n,m,cnt;
inline void add(int x,int y)
{
    tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot;
}
inline void add1(int x,int y)
{
    tot++; a[tot]=y; nxt[tot]=point[x]; point[x]=tot;
}
void dfs(int x,int val)
{
    if(dis[x]>=0) return;
    dis[x]=val; que.push(x);
    for(int i=point[x];i!=-1;i=nxt[i]) dfs(a[i],val);
    if(x>=cnt) return;
    for(int i=0;i<20;++i)
     if((x>>i)&1) dfs(x^(1<<i),val);
}
int main()
{
    int i,j;
    cnt=1<<20;
    memset(p,-1,sizeof(p));
    memset(nxt,-1,sizeof(nxt));
    memset(point,-1,sizeof(point));
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) 
     {
        int x;
        scanf("%d",&x);
        add(cnt+i,x); add1(x,cnt+i);
     }
    for(i=1;i<=m;++i)
     {
        int x,y;
        scanf("%d%d",&x,&y);
        add(cnt+x,cnt+y);
     }
    memset(dis,-1,sizeof(dis));
    dfs(cnt+1,0);
    while(!que.empty())
     {
        int u=que.front(); que.pop();
        for(i=p[u];i!=-1;i=nxt[i]) dfs(a[i],dis[u]+1);
     }
    for(i=1;i<=n;++i) printf("%d\n",dis[cnt+i]);
    return 0;
}