[NOIP校内集训]home

题意

求一张图中的割点，且该割点可以分开(1)和(n)（(1)和(n)除外）

思路

神奇的思路，值得思考

在求割点的基础上，题目要求要将(1)和(n)分开；我们随便找一条从(1)到(n)的简单路径，将其打上(flag)标记，有结论：一个点(rt)（(1)和(n)除外）是满足条件的点，当且仅当在(dfs)树上它的一个儿子(v)满足((low_{v}geq dfn_{rt}) && (sign_v))

证明：若有(low_{v}geq dfn_{rt})，则说明(rt)这个割点可以将(rt)和(v)所在连通块分开，由于(1)在(rt)的连通块内，而(n)在(v)的连通块内（为什么(n)不会在(rt)的连通块内呢？因为如果存在一条路径从(1)到(v)再到(n)，那么它必然会经过(rt)两次（注意(rt)是割点，即从(v)到(rt)的连通块必经(rt)），这和上面简单路径的定义矛盾），所以该割点将(1)和(n)分开

代码很简单，只用在求割点的基础上加三行代码，而由于只用管(1)和(n)的连通块，只用(tarjan(1))一次且不用判断根是不是割点

Code

#include<bits/stdc++.h>
#define N 200005 
#define M 400005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int T,n,m,root;
int dfn[N],low[N],c;
int st[N],top;
bool cutpoint[N],sign[N];

struct Edge
{
	int next,to;
}edge[M<<1];int head[N],cnt;
inline void add_edge(int from,int to)
{
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	head[from]=cnt;
}
template <class T>
void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void init()
{
	memset(head,0,sizeof(head));
	memset(cutpoint,0,sizeof(cutpoint));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(sign,0,sizeof(sign));
        //反正又不会超时，初始化随意（
	top=c=0; cnt=1;
	
	read(n);read(m);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		read(x);read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
}
void tarjan(int u)
{
	dfn[u]=low[u]=++c; if(u==n) sign[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			sign[u]|=sign[v];
			if(low[v]>=dfn[u]&&sign[v]&&u!=1) cutpoint[u]=1,++top;
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int main()
{
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	read(T);
	while(T--)
	{
		init();
		tarjan(1);
		printf("%d
",top);
		for(int i=2;i<n;++i) if(cutpoint[i]) printf("%d ",i);
		printf("
");
	}
	return 0;
}