Submission #49633059

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
vector<pair<int,int> > g[200010]; // u->{v,eid}
vector<pair<int,int> > g2[200010]; // groupu -> {groupv,old eid}

int dep[200010];
int mindep[200010];
array<int,2> edge[200010];
bool vis[200010];
int key[200010];
void dfs(int u,int fa,int d){
  vis[u]=true;
  dep[u] = d;
  mindep[u]=d;
  for(auto &[v,eid]:g[u]) if(v!=fa){
    if(!vis[v]) dfs(v,u,d+1);
    if(mindep[v] > dep[u]) {
      // printf("keypath : %d -> %d\n",u,v);
      key[eid] = true;
    }
    mindep[u] = min(mindep[u],mindep[v]);
  }
  // printf("dep[%d]=%d, mindep[%d]=%d\n",u,dep[u],u,mindep[u]);
}
int uf[200010];
int getfa(int u){ return uf[u]==u?u:uf[u]=getfa(uf[u]); }
void dfs2(int u, int fa){
  vis[u] = true;
  for(auto &[v,eid]:g[u]) if(v!=fa){
    if(!vis[v]) dfs2(v,u);
    if(!key[eid]) {
      // printf("link %d <-> %d\n",u,v);
      uf[getfa(u)] = getfa(v);
  }
  }
}

bool dfs3(int u,int fa,int dst, vector<int>&path){
  assert(u==getfa(u));
  if(u==dst) {
    return true;
  }
  vis[u]=true;
  for(auto [v,eid]:g2[u]) if(getfa(v) != fa and !vis[v]) {
    assert(key[eid]);
    bool ret = dfs3(getfa(v),u,dst,path);
    if(ret) {// u->v能找到dst
      path.push_back(eid);
      return ret;
    }
  }
  return false;

}

int main(){
  int n=read();
  int m=read();
  int a=read()-1;
  int b=read()-1;
  int c=read()-1;
  int eid = 0;
  rep(i,0,m) {
    int u=read()-1;
    int v=read()-1;
    g[u].push_back({v,eid});
    g[v].push_back({u,eid});
    edge[eid]={u,v};
    eid++;
  }
  // 找关键路径
  dfs(0,0,0);
  // 合并非关键路径上的点
  iota(uf,uf+n,0);
  fill(vis,vis+n,false);
  dfs2(0,0);

  rep(u,0,n) {
    int fu=getfa(u);
    for(auto [v,eid]:g[u]) {
      int fv = getfa(v);
      if(fv != fu) g2[fu].push_back({fv,eid}); // 可能重边
    }
  }
  // rep(u,0,n) if(u==getfa(u)){
  //   sort(begin(g2[u]),end(g2[u]));
  // }

  // 新的树上做简单路径查找
  fill(vis,vis+n,false);
  vector<int> path; // path是所有eid list, 从c到a的 eid list, 因为是递归push的所以方向相反
  dfs3(getfa(a),getfa(a),getfa(c),path); // 一定全是key 路径

  vector<int> vertexs = {c};
  for(auto eid:path){
    auto [u,v] = edge[eid];
    if(getfa(u) == getfa(vertexs.back())){
      vertexs.push_back(u); // -u-v-
      vertexs.push_back(v); // -u-v-
    }else{
      assert(getfa(v) == getfa(vertexs.back()));
      vertexs.push_back(v); // -u-v-
      vertexs.push_back(u); // -u-v-
    }
  }
  vertexs.push_back(a);
  // for(auto vertex:vertexs) printf("%d -> ",vertex);
  for(int i=0;i<(int)size(vertexs);i+=2) if(getfa(b) == getfa(vertexs[i])) {
    if(vertexs[i] != vertexs[i+1]) { // ===?-b-?===
      printf("Yes\n");
      return 0;
    }else{
      if(vertexs[i] == b) { // ===b===
        printf("Yes\n");
        return 0;
      }
    }
  }
  printf("No\n");
  return 0;
}

// 简单无向连通图N点，m边
// n 2e5
// m 2e5
// 判断是否有简单路径连接 a,b,c三个点（保证不同)
// 如果是树，也就是u..v的简单路径上 或者u外侧，v外侧
// 或者是选一个点，其它点在分开的3个子树里
// 如果两点在一个环上， 那么第三点 到最近的环的点连线再绕一圈一定是方案
// 否则a,b,c任意两点不在任何环上
// 说明 a...b 的路径中有至少一个关键边????
// 如果a..b存在两条无重复的路径，则在环上，
// 否则a..b的所有路径两两有重复边
// 如果没有关键路径，那么 去掉每条边依然连通，可以构造出一条新路径
// 所以找 关键路径
// 对非关键路径 并查集缩点，最后就是树上判断
// dfs(u,fa)
//  minvis[u] = u;
//  for v in e[u] and v != fa:
//    minvis[u] = min(dfs(v,u))
// 关键路径满足dfs能访问的点的最小深度 = u?

Submission Info

Compile Error

Main.cpp: In function ‘ll read()’:
Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result