[HNOI2019]校园旅行(构造+生成树+动规)

题目

[HNOI2019]校园旅行

做法

最朴素的做法就是点对扩展\(O(m^2)\)

发现\(n\)比较小，我们是否能从\(n\)下手减少边数呢？是肯定的

单独看一个颜色的联通块，如果是二分图，我们生产树和原来的效果相同

如果不是二分图，是会有一个环的，在树上随便圈一个自环和原来的效果相同

而看不同颜色的连边，一定是二分图，再生产树就好了

总边数是\(n\)级的，总复杂度\(O(n^2)\)

Code

#include<bits/stdc++.h>

#include<queue>

typedef int LL;

const LL maxn=5009,maxm=500009;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3)+(x<<1)+c-'0'; c=getchar();

	}

	return x*f;

}

LL f;

LL visit[maxn],col[maxn],a[maxn],fa[maxn];

LL n,m,q,top;

LL mark[maxn][maxn];

struct edge{

	LL u,v;

}e[maxm];

LL Get_fa(LL x){

	return fa[x]==x?x:fa[x]=Get_fa(fa[x]);

}

struct Mp{

	struct node{

		LL to,nxt;

	}dis[maxm<<1];

	LL num;

	LL head[maxn];

	inline void Add(LL u,LL v){

		dis[++num]=(node){v,head[u]}; head[u]=num;

	}

	void Dfs1(LL u,LL c){

		visit[u]=true; col[u]=c;

		for(LL i=head[u];i;i=dis[i].nxt){

			LL v(dis[i].to);

			if(a[v]!=a[u]) continue;

			if(visit[v]){

				if(col[v]==col[u]) f=true;

				continue;

			}

			LL fx(Get_fa(u)),fy(Get_fa(v));

			if(fx!=fy){

                fa[fx]=fy;

				e[++top]=(edge){u,v};

			}

			Dfs1(v,3-c);

		}

	}

	void Dfs2(LL u){

		visit[u]=true;

		for(LL i=head[u];i;i=dis[i].nxt){

			LL v(dis[i].to);

			if(a[v]==a[u] || visit[v]) continue;

            LL fx(Get_fa(u)),fy(Get_fa(v));

            if(fx!=fy){

            	e[++top]=(edge){u,v};

            	fa[fx]=fy;

		    }

			Dfs2(v);

		}

	}

}G1,G2;

std::queue<edge> que;

inline void Build(){

	for(LL i=1;i<=n;++i) fa[i]=i;

	for(LL i=1;i<=n;++i){

		if(!visit[i]){

		    f=false;

		    G1.Dfs1(i,1);

		    if(f) G2.Add(i,i);

		}

	}

	memset(visit,false,sizeof(visit));

	for(LL i=1;i<=n;++i) fa[i]=i;

	for(LL i=1;i<=n;++i)

	    if(!visit[i])

	        G1.Dfs2(i);

	for(LL i=1;i<=top;++i){

		LL u(e[i].u),v(e[i].v);

		G2.Add(u,v); G2.Add(v,u);

	}

	for(LL u=1;u<=n;++u){

		que.push((edge){u,u}); mark[u][u]=true;

		for(LL i=G2.head[u];i;i=G2.dis[i].nxt){

			LL v(G2.dis[i].to);

			if(a[v]==a[u]){

				que.push((edge){v,u});

				mark[v][u]=mark[u][v]=true;

			}

		}

	}

	while(que.size()){

		edge tmp(que.front()); que.pop();

		LL u(tmp.u),v(tmp.v);

		for(LL i=G2.head[u];i;i=G2.dis[i].nxt){

			LL v1(G2.dis[i].to);

			for(LL j=G2.head[v];j;j=G2.dis[j].nxt){

				LL v2(G2.dis[j].to);

				if(a[v1]==a[v2]){

					if(!mark[v1][v2]){

						mark[v1][v2]=mark[v2][v1]=true;

						que.push((edge){v1,v2});

					}

				}

			}

		}

	}

}

char s[maxn];

int main(){

	n=Read(),m=Read(),q=Read();

	scanf(" %s",s+1);

	for(LL i=1;i<=n;++i) a[i]=s[i]-'0';

	while(m--){

		LL u(Read()),v(Read());

		G1.Add(u,v); G1.Add(v,u);

	}

	Build();

	while(q--){

		LL u(Read()),v(Read());

		if(mark[u][v]) puts("YES");

		else puts("NO");

	}

    return 0;

}