网站搜索引擎关键字怎么做,网站app在线生成器,红色系 网站,佛山网站制作网站设计CF639F Bear and Chemistry
Solution
显然题目的条件就是所有点在一个边双连通分量内。
所以我们先缩边双求出边双树。
然后对于每一个询问#xff0c;对询问的点和边的端点建虚树#xff0c;然后把询问的边连上跑tarjantarjantarjan求边双判断是否所有询问点在同一个边双…CF639F Bear and Chemistry
Solution
显然题目的条件就是所有点在一个边双连通分量内。
所以我们先缩边双求出边双树。
然后对于每一个询问对询问的点和边的端点建虚树然后把询问的边连上跑tarjantarjantarjan求边双判断是否所有询问点在同一个边双内即可。
时间复杂度O((nm)lgn)O((nm)lgn)O((nm)lgn)。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
PR _E[MAXN],ex[MAXN];
vectorint E[MAXN];
int nn,R0,edgenum1,head[MAXN],dfn[MAXN],low[MAXN],instk[MAXN],a[MAXN],b[MAXN],idnum,num,top;
int col[MAXN],colnum,DFN,_Enum,Dfn[MAXN],dep[MAXN],fa[MAXN][20],Log[MAXN],vis[MAXN],stk[MAXN],id[MAXN],N,M,n,m,Case;
struct enode{ int to,nxt; } e[MAXN];int rotate(int element)
{element(elementR)%nn;if (!element) elementnn;return element;
}
void add(int u,int v) { /*coutu-vendl;*/ e[edgenum](enode){v,head[u]},head[u]edgenum; }
void tarjan(int x,int lst)
{instk[x]1,dfn[x]low[x]DFN;for (int ihead[x];i;ie[i].nxt){int ve[i].to;if (ilst||i(lst^1)) continue;
// coutx vendl;if (!dfn[v]) tarjan(v,i),upmin(low[x],low[v]);else if (instk[v]) upmin(low[x],dfn[v]);}for (int ihead[x];i;ie[i].nxt){int ve[i].to;if (ilst||i(lst^1)) continue;if (low[v]dfn[x]) E[x].PB(v),E[v].PB(x);else _E[_Enum]MP(x,v);}instk[x]0;
// coutx dfn[x] low[x]endl;
}
void dfs(int x)
{col[x]colnum;for (auto v:E[x]) if (!col[v]) dfs(v);
}
void dfs1(int x,int father)
{Dfn[x]DFN,dep[x]dep[father]1,fa[x][0]father;for (int i1;iLog[dep[x]];i) fa[x][i]fa[fa[x][i-1]][i-1];for (int ihead[x];i;ie[i].nxt) if (!Dfn[e[i].to]) dfs1(e[i].to,x);
}
int getlca(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int iLog[dep[x]];i0;i--)if (dep[fa[x][i]]dep[y]) xfa[x][i];if (xy) return x;for (int iLog[dep[x]];i0;i--)if (fa[x][i]!fa[y][i]) xfa[x][i],yfa[y][i];return fa[x][0];
}void Add(int u,int v) { add(u,v),add(v,u); }
void DFS(int x)
{vis[x]1;for (auto v:E[x]) if (!vis[v]) DFS(v);
}
void solve(int T)
{for (int i1;iM;i) Add(ex[i].fi,ex[i].se);_EnumDFN0,tarjan(a[1],0),DFS(a[1]);int flag1;for (int i1;iN;i) if (!vis[a[i]]) flag0;puts(flag?YES:NO);if (flag) R(RT)%nn;edgenum1;for (int i1;iidnum;i) head[id[i]]vis[id[i]]low[id[i]]dfn[id[i]]0,E[id[i]].clear();
}
void build()
{top0,idnum0;for (int i1;inum;i){if (!top) { stk[top1]b[i],id[idnum]b[i]; continue; }int lcagetlca(stk[top],b[i]);if (!lca) { while (top1) Add(stk[top-1],stk[top]),top--;stk[top1]b[i],id[idnum]b[i]; continue; }while (top1dep[stk[top-1]]dep[lca]) Add(stk[top-1],stk[top]),top--;if (dep[stk[top]]dep[lca]) Add(lca,stk[top--]);if (stk[top]!lca) stk[top]lca,id[idnum]lca;stk[top]b[i],id[idnum]b[i];}while (top1) Add(stk[top-1],stk[top]),top--;
}
signed main()
{nnnread(),mread(),Caseread();for (int i1;im;i) {int uread(),vread();if (u!v) Add(u,v);}for (int i1;in;i) if (!dfn[i]) tarjan(i,0);for (int i1;in;i) if (!col[i]) colnum,dfs(i);edgenum1;for (int i1;in;i) head[i]0;for (int i1;i_Enum;i) Add(col[_E[i].fi],col[_E[i].se]);ncolnum,dep[0]-1,Log[1]0,DFN0;for (int i2;in;i) Log[i]Log[i1]1;for (int i1;in;i) if (!Dfn[i]) dfs1(i,0);edgenum1;for (int i1;in;i) head[i]dfn[i]low[i]0,E[i].clear();for (int T1;TCase;T){Nread(),Mread(),numN;for (int i1;iN;i) a[i]rotate(read());for (int i1;iM;i) ex[i].firotate(read()),ex[i].serotate(read());for (int i1;iN;i) a[i]b[i]col[a[i]];for (int i1;iM;i) ex[i]MP(col[ex[i].fi],col[ex[i].se]),b[num]ex[i].fi,b[num]ex[i].se;sort(a1,aN1,[](int x,int y){ return Dfn[x]Dfn[y]; }),Nunique(a1,aN1)-a-1;sort(b1,bnum1,[](int x,int y){ return Dfn[x]Dfn[y]; }),numunique(b1,bnum1)-b-1;build(),solve(T);}return 0;
}
