自动搬运

查看原文

来自洛谷，原作者为

	liuzhongrui **

搬运于2025-08-24 22:03:43，当前版本为作者最后更新于2023-10-28 18:03:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

很明显，一道图论题，我在拿了 $61$ 分后看了下封禁大佬的代码，茅塞顿开，分享一下我的收获与理解。

思路

• 首先，我们需要构建图的邻接表表示。根据输入的边信息，我们可以构建一个邻接表，其中每个节点表示为一个邻接列表，包含与该节点相邻的节点。

• 接下来，我们使用深度优先搜索来搜索一条满足条件的路径。我们从任意一个节点开始，使用 DFS 遍历图中的节点，并记录下当前路径上的节点顺序。在遍历过程中，我们需要满足以下条件：

    1. 当前路径上的节点数量至少为四。
    2. 当前路径上的节点顺序与题目要求一致。
    3. 当前路径上的节点之间存在边连接。
  

• 如果找到满足条件的路径，我们将其输出；否则，输出 no。

实现

使用 Tarjan 算法进行深度优先搜索，找出所有被访问过的节点，并记录下这些节点的最低入度，使用广度优先搜索，从指定的节点开始，找到所有与该节点相连的节点，并记录下这些节点的编号。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair<int,int>
const int mod=1e9+7,N=200005,M=1003;
int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(int x) {
	if(x<0)x=-x,putchar('-');
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
struct st {
	int v,id;
	st() {} st(int A,int B) {
		v=A,id=B;
	}
};
int n,m,cnt;
vector<st>G[M];
vector<int>V[N];
int b[M][M];
int sta[N],top;
int col[N],color;
int dfn[N],low[N],tot;
int eu[N],ev[N];
int Sha;
void Tarjan(int x) {
	dfn[x]=low[x]=++tot;
	sta[++top]=x;
	for(auto y:V[x]) {
		if(!dfn[y]) {
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		} else if(!col[y])low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]) {
		if(sta[top]!=x)Sha=x;
		col[x]=1;
		while(sta[top]!=x)col[sta[top]]=1,top--;
		top--;
	}
}
vector<int>Ans;
int pre[N];
void bfs(int s) {
	queue<int>Q;
	Q.push(s);
	pre[s]=-1;
	while(!Q.empty()) {
		int x=Q.front();
		Q.pop();
		for(auto y:V[x]) {
			if(y==pre[x])continue;
			if(!pre[y]) {
				pre[y]=x;
				Q.push(y);
			} else if(y==s) {
				int now=x;
				while(now>0) {
					Ans.push_back(ev[now]);
					now=pre[now];
				}
				for(auto t:Ans)write(t),putchar(' ');
				exit(0);
			}
		}
	}
}
signed main() {
	n=read(),m=read();
	for(int i=1; i<=m; i++) {
		int x=read(),y=read();
		b[x][y]=b[y][x]=1;
		G[x].push_back(st(y,i)),G[y].push_back(st(x,i+m));
		eu[i]=x,ev[i]=y;
		eu[i+m]=y,ev[i+m]=x;
	}
	for(int i=1; i<=n; i++) {
		for(auto x:G[i]) {
			for(auto y:G[x.v]) {
				if(b[i][y.v]||y.v==i)continue;
				V[x.id].push_back(y.id);
			}
		}
	}
	for(int i=1; i<=2*m; i++)if(!dfn[i])Tarjan(i);
	if(!Sha)puts("no");
	else bfs(Sha);
	return 0;
}