Submission #68195328

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std; 
signed main() {
  int t; 
  cin>>t;
  
  function<int(vector<int>&,int)> gp = [&](vector<int> & p, int u) {
    return p[u] == u? u: p[u] = gp(p, p[u]); 
  };
  
  auto merge = [&](vector<int>& p, int u, int v) {
    auto p1 = gp(p,u), p2 = gp(p,v);
    p[p1] = p2; 
  };
  
  auto same = [&](vector<int> & p,int u, int v) -> bool {
    return gp(p,u) == gp(p,v); 
  };
  while(t--) {
    int n; 
    cin>>n; 
    int m; 
    cin>>m;
    int x,y; 
    cin>>x>>y; 
    x--; y--;
    vector<vector<int>> g(n); 
    for(int i=0;i<m;i++) {
      int u,v; 
      cin>>u>>v; 
      u--; v--; 
      g[u].push_back(v);
      g[v].push_back(u); 
    }
    for(int i=0;i<n;i++) sort(g[i].begin(), g[i].end()); 
    vector<bool> vis(n, false);
    vector<int> p(n, -1);  
    function<bool(int)> dfs = [&](int u) {
      if (u == y){
        vis[u] = true; 
        return true; 
      }
      vector<int> par(n);
      iota(par.begin(), par.end(),0); 
      for(int i=0;i<n;i++) {
        if(vis[i])continue; 
        for(auto v:g[i]) {
          if (vis[v])continue; 
          merge(par, i,v); 
        }
      }
      if (!same(par, u, y)) return false; 
      vis[u] = true; 
      for(auto v:g[u]) {
        if (vis[v])continue;
        p[v] = u; 
        if (!dfs(v)) {
          p[v] = -1; 
          continue; 
        }
        return true; 
      }
      return false;
    };
    dfs(x); 
    int cur = y;
    deque<int> ans; 
    while(cur!=-1) {
      ans.push_front(cur); 
      cur = p[cur]; 
    }
    for(auto i: ans) { cout<< i + 1 << " "; }
    cout<<endl; 
  }
}

Submission Info

Judge Result