一流小说网站模板,老板合作网站开发,重庆seo,设计行业网站匹配 哈希能A 水到爆炸 回家 事实上我做过一个原题#xff0c;甚至比这个回家难的多#xff0c;而且那个题多组询问必经点 然后我做一组询问就打炸了 大约就是删了很多东西#xff0c;然后自己想的太简单了 直接统计了割点#xff0c;懒得打lca和树上差分#xff0c;懒得打… 匹配 哈希能A 水到爆炸 回家 事实上我做过一个原题甚至比这个回家难的多而且那个题多组询问必经点 然后我做一组询问就打炸了 大约就是删了很多东西然后自己想的太简单了 直接统计了割点懒得打lca和树上差分懒得打dfs偷懒让我付出很大代价 最后只有10 打代码一定不能偷懒一定不能偷懒 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 810000
ll dfn[A],low[A],ver[A],nxt[A],head[A],s[A],fa[A],belong[A],kx[A];
ll Head[A],Nxt[A],Ver[A],To[A],vst[A];
ll tot0,tot20,num0,n,m,t,root;
vectorll dcc[A],ans;
bool cut[A];
void add(ll x,ll y){nxt[tot]head[x],head[x]tot,ver[tot]y;
}
void Add(ll x,ll y){Nxt[tot2]Head[x],Head[x]tot2,Ver[tot2]y;
}
inline ll read(){ll f1,x0;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)(c-0);cgetchar();}return f*x;
}
void tarjan(ll x)
{ll flag0;dfn[x]low[x]tot;s[s[0]]x;for(ll ihead[x];i;inxt[i]){ll yver[i];if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);if(low[y]dfn[x]){flag;num;if(flag1||x!root)cut[x]1;while(s[0]){ll ps[s[0]--];dcc[num].push_back(p);if(py)break;}dcc[num].push_back(x);}}else low[x]min(low[x],dfn[y]);}
}
void dfs(ll x)
{if(xbelong[n])return ;vst[x]1;for(ll iHead[x];i;iNxt[i]){ll yVer[i];if(vst[y])continue;fa[y]x;dfs(y);}return ;
}
void re(){num0,tot0;ans.clear();tot20;for(ll i0;i800000;i) dcc[i].clear();memset(nxt,0,sizeof(nxt));memset(Head,0,sizeof(Head));memset(Nxt,0,sizeof(Nxt));memset(fa,0,sizeof(fa));memset(vst,0,sizeof(vst));memset(head,0,sizeof(head));memset(ver,0,sizeof(ver));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(cut,0,sizeof(cut));memset(kx,0,sizeof(kx));
}
int main()
{tread();while(t--){re();nread(),mread();for(ll i1;im;i){ll xread(),yread();add(x,y);add(y,x);}for(ll i1;in;i)if(!dfn[i]) rooti,tarjan(i);ll nunum;for(ll i1;in;i)if(cut[i])belong[i]nu,kx[nu]i;for(ll i1;inum;i)for(ll j0;jdcc[i].size();j){ll xdcc[i][j];if(cut[x]) Add(belong[x],i),Add(i,belong[x]);else belong[x]i;}
/* for(ll i1;in;i){coutbelongbelong[i]endl;}
*/ dfs(belong[1]);ll xfa[belong[n]];while(x!belong[1]){if(x0) break;if(xnum) ans.push_back(kx[x]);xfa[x];}printf(%lld\n,1ll*ans.size());sort(ans.begin(),ans.end());for(ll i0;ians.size();i)printf(%lld ,ans[i]);coutendl;}
} 转载于:https://www.cnblogs.com/znsbc-13/p/11248153.html
