ABC g 求 hack
  • 板块题目总版
  • 楼主xiaoming007
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/9/2 21:43
  • 上次更新2023/11/2 23:46:42
查看原帖
ABC g 求 hack
938449
xiaoming007楼主2023/9/2 21:43
#include <bits/stdc++.h>
const int N = 1e6 + 10;
#define int long long
using namespace std;
int n, m, s, t, g, flg;
bool vis[N];
vector<int> e[N];
bool _[N], p[N];
int dfs(int k, bool viag) {
	if (p[k]){
		if(p[k]==2&&viag)flg=1;
		return p[k];
	}
	if (flg)return 2;
	if (k == t) {
		if (viag == 1) {
			flg=1;
		}
		return 2;
	}
	int l = e[k].size();
	for (int i = 0; i < l; ++i) {
		int v = e[k][i];
		if (vis[v])continue;
		vis[v] = 1;
		if(dfs(v, viag || (v == g)) == 2)p[k]=2;
		vis[v] = 0;
	}
	if(!p[k])p[k] = 1;
	return p[k];
}
signed main() {
	scanf("%lld %lld", &n, &m);
	scanf("%lld %lld %lld", &s, &g, &t);
	while (m--) {
		int u, v;
		scanf("%lld %lld", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	vis[s] = 1;
	dfs(s,s==g);
	if (flg) puts("Yes");
	else puts("No");
	return 0;
}

2023/9/2 21:43
加载中...