题解
第一眼,板子题,不就是一个缩点吗?后来一想不对,哪有这么傻的出题人呢,出个这水题。
一想，不对，不仅要求割点，还要判断这个割点是否在搜索树 \(n\) 的祖先上。想到这后，我哈哈大笑，还想坑我，我早就识破了你轨迹。
啪啪打脸。考完才发现是我天真了。搜索树上不一定只包含必经点，因为搜索顺序问题，我们还会因为有环多算上点。所以我们要进行缩点。
缩点后我们就可以保证无环且是棵数了。
其实避免这种情况有两种方法：
１.我们在 $tajan$ 完后的搜索树上从根跳算对于 $n$ 的割点，而不是整个图的割点
2.缩点
注意我们只用判自环而不用判重边，在 \(tarjan\) 的时候判一下就行，减小常数。
\(AC\kern 0.4emCODE:\)
Code
#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define pb(x) push_back(x)
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
static const int N=3.4e5+7;
int dfn[N],low[N],cut[N],first[N],f[N],st[N],id[N],be[N],bac[N],T,rt,tot,cnt,num,cntd,t=1,n,m,tp;
struct edge{int v,nxt;}e[N<<2];
vector<int> dcc[N];
inline void add(int u,int v) {
e[t].v=v;
e[t].nxt=first[u];
first[u]=t++;
}
void dfst(int x,int last) {
dfn[x]=low[x]=p(tot);
int fg=0;
st[p(tp)]=x;
for (ri i(first[x]),v;i;i=e[i].nxt) {
if (!dfn[v=e[i].v]) {
dfst(v,x);
low[x]=cmin(low[x],low[v]);
if (low[v]>=dfn[x]) {
p(fg);
if (x!=rt||fg>1) cut[x]=1;
p(cnt);
int tmp;
while((tmp=st[tp--])!=v) dcc[cnt].pb(tmp);
dcc[cnt].pb(v);dcc[cnt].pb(x);
}
} else if(v!=last) low[x]=cmin(low[x],dfn[v]);
}
}
void dfs(int x,int fa) {
f[x]=fa;
for (ri i(first[x]),v;i;i=e[i].nxt) {
if ((v=e[i].v)==fa) continue;
dfs(v,x);
}
}
inline void init() {
memset(first,0,sizeof(first));
cntd=cnt=tot=tp=0,t=1;
for (ri i(1);i<=n;p(i)) dcc[i].clear();
memset(cut,0,sizeof(cut));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(be,0,sizeof(be));
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
T=read();
for (ri z(1);z<=T;p(z)) {
n=read(),m=read();
init();
for (ri i(1);i<=m;p(i)) {
int u=read(),v=read();
if (u==v) continue;
add(u,v);add(v,u);
}
for (ri i(1);i<=n;p(i)) if (!dfn[i]) rt=i,dfst(i,0);
t=1;num=cnt;
memset(first,0,sizeof(first));
for (ri i(1);i<=n;p(i)) if (cut[i]) id[i]=p(num),bac[num]=i;
for (ri i(1);i<=cnt;p(i)) {
for (ri j(0);j<dcc[i].size();p(j)) {
int x=dcc[i][j];
if (cut[x]) add(id[x],i),add(i,id[x]);
else be[x]=i;
}
}
if (cut[1]) dfs(id[1],0);
else dfs(be[1],0);
int x=cut[n]?f[id[n]]:f[be[n]];
while(f[x]) {
if (x>cnt) cut[bac[x]]=2,p(cntd);
x=f[x];
}
printf("%d\n",cntd);
for (ri i(cnt+1);i<=num;p(i)) if (cut[bac[i]]==2) printf("%d ",bac[i]);
puts("");
}
return 0;
}
}
int main() {return nanfeng::main();}