首页 > 其他分享 >abc318_g Typical Path Problem 题解 圆方树

abc318_g Typical Path Problem 题解 圆方树

时间:2024-11-01 19:21:52浏览次数:4  
标签:abc318 int 题解 d% tot 圆方树 maxn low dfn

题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g

题目大意:

给出一个有 \(n\) 个顶点和 \(m\) 条边的无向连通图 \(G\),没有重边和自环。

顶点的编号为 \(1 \sim n\),边的编号为 \(1 \sim m\),第 \(i\) 条边连接顶点 \(u_i\) 和 \(v_i\)。

给出图上三个不同的顶点 \(A,B,C\)。判断是否有从点 \(A\) 经过点 \(B\) 到点 \(C\) 的简单路径。

简单路径指路径上的点互不相同,即不重复经过同一个点。

解题思路:

建立圆方树。则在 \(A\) 点到 \(C\) 点的路径中存在点 \(B\) 或者存在与点 \(B\) 邻接的方点,答案为 Yes;否则为 No

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;

int n, m, A, B, C, dfn[maxn], low[maxn], idx, tot, fa[maxn];
stack<int> stk;
vector<int> g[maxn], G[maxn];
bool vis[maxn];

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk.push(u);
    for (auto v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (low[v] == dfn[u]) {
                fa[++tot] = u;
                G[u].push_back(tot);
                int x;
                do {
                    x = stk.top();
                    stk.pop();
                    fa[x] = tot;
                    G[tot].push_back(x);
                } while (x != v);
            }
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    tot = n;
    tarjan(A);
    bool flag = false;
    for (int u = C; u && !flag; u = fa[u]) {
        if (u == B) flag = true;
        if (u > n) {
            for (auto v : G[u])
                if (v == B)
                    flag = true;
        }
    }
    puts(flag ? "Yes" : "No");
    return 0;
}

标签:abc318,int,题解,d%,tot,圆方树,maxn,low,dfn
From: https://www.cnblogs.com/quanjun/p/18521097

相关文章

  • 《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3
    T1统计得分内存限制: 256 Mb时间限制: 1000 ms题目描述在一场知识竞赛中,选手答对一题得 11 分,答错不得分且要倒扣 11 分,但扣分不能让分数小于 00。给定一个由 Y 及 N 构成的字符序列,答对记为 Y,答错记为 N。选手一开始从 00 分开始,请输出选手最后的得分......
  • 思维题配套题解
    配套题单:CodeForces思维题目CF79DPassword你有\(n\)个灯泡,一开始都未点亮。同时你有\(l\)个长度,分别为\(a_1\sima_l\)。每次你可以选择一段连续的子序列,且长度为某个\(a_i\),并将这些灯泡的明灭状态取反。求最少的操作次数,使得最后有且仅有\(k\)个位置是亮的,......
  • 题解 洛谷 Luogu P1308 [NOIP2011 普及组] 统计单词数 C++
    题目传送门:P1308[NOIP2011普及组]统计单词数-洛谷|计算机科学教育新生态https://www.luogu.com.cn/problem/P1308getline() 会清除使当次getline() 终止的换行,而cin 不会因此cin 以换行终止,之后还需要getline()的话,需要用getchar() 吞换行Linux的一些相......
  • P11228 [CSP-J 2024] 地图探险 题解
    模拟第一眼,可能有人回想起dfs.但因为起点终点,并且走的步数都告诉你了,所以直接模拟就行.注意起始点也算被走过,所以可以用一个标记数组,判断当前格子有没有被走过.代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;int......
  • AtCoder Beginner Contest 376 题解
    AtCoderBeginnerContest376题解AtCoderBeginnerContest376A-CandyButton#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;voidsolve(){ intn,c;cin>>n>>c; intpre=-1; intans=0; for(inti=1;i<=n;i++)......
  • 洛谷 P2606 [ZJOI2010] 排列计数 题解
    题目链接[ZJOI2010]排列计数-洛谷题解看到\(p_i>p_{\lfloori/2\rfloor}\)这个条件,可能一开始不会有什么想法。但是如果我们换种写法,即:\(p_i<p_{2i}\landp_i<p_{2i+1}\)。这样我们就能很容易看出来,这是小根堆的形式。现在我们从根节点开始考虑,假设左子树的大小......
  • P1779 魔鬼杀手 题解&&思路
    P1779魔鬼杀手题解&&思路题目链接。分析题目性质我们发现假如有状态表示\(M\)个方案选或不选,那么这个状态有唯一确定的结果,即结果不会随着施法的顺序而改变。考虑\(dp.\)我们从题目出发,发现每个方案有单个攻击或者集体攻击,想一想从这个方面考虑。又由于每一个方案是可......
  • 洛谷Python顺序结构题解合集
    P5705【深基2.例7】数字反转a=s[0]b=s[1]c=s[2]d=s[4]print(f"{d}.{c}{b}{a}")P5706【深基2.例8】再分肥宅水ans=float(a[0])/int(a[1])beizi=2*int(a[1])print(f"{ans:.3f}\n{beizi}")P5708【深基2.习2】三角形面积p=0.5*(a+b+c)ans=pow((p*(p-a)*(p-b)*(p-c)),0.5......
  • Navicat 连接 MySQL 失败:2002-can‘t connect to server on localhost(10061)问题解决
    连接不上问题可能有如下原因服务器安全组中没有配置3306端口mysql服务端口只开放本地了如下:修改/etc/mysql/mysql.conf.d/mysqld.cnf中bind-address和mysqlx-bind-address注释掉重启mysql服务systemctlrestartmysqlmysql登录用户的host为localhost只允......
  • CATIA许可证常见问题解答
    在使用CATIA软件的过程中,许可证问题常常是用户关心的焦点。为了帮助大家更好地理解和解决这些问题,我们整理了一份CATIA许可证常见问题解答,希望能为您提供便捷的参考。问题一:如何激活CATIA许可证?解答:激活CATIA许可证通常需要访问软件的官方平台或使用特定的许可证管理工具。您需......