C++(clang++ 11.0.1) 解法, 执行用时: 29ms, 内存消耗: 808K, 提交时间: 2022-12-06 20:57:04

#include <bits/stdc++.h>
using namespace std;
auto solve(){
  int n, m;
  cin>>n>>m;
  vector<pair<int,int>> edg(m);
  for(auto &[u,v]: edg){
    cin>>u>>v;
    u--, v--;
  }
  vector<int> v(n), id(n);
  for(auto &i: v){
    cin>>i;
    i--;
  }
  if(n >= 3 && m > 3 * n - 6){
    cout<<"NO\n";
    return;
  }
  for(int i = 0 ; i < n; ++i){
    id[v[i]] = i;
  }
  vector<pair<int,int>> e;
  for(auto &[u, v]: edg){
    if(max(id[u], id[v]) - min(id[u], id[v]) == 1 || max(id[u], id[v]) - min(id[u], id[v]) == n-1){
      continue;
    }
    e.emplace_back(id[u], id[v]);
  }
  if(e.size() == 0){
    cout<<"YES\n";
    return;
  }
  vector<vector<int>> E(e.size());
  vector<int> col(e.size(), -1);
  for(int i = 0 ; i < (int) e.size(); ++i){
    for(int j = i+1; j < (int) e.size(); ++j){
      auto [u,v] = e[i];
      if(u > v) swap(u,v);
      auto [x,y] = e[j];
      if(x > y) swap(x,y);
      if((u < x && x < v && v < y) || (x < u && u < y && y < v)){
        E[i].emplace_back(j);
        E[j].emplace_back(i);
      }
    }
  }
  bool flag = false;
  function<void(int, int)> dfs = [&](int u, int c){
    if(col[u] == -1){
      col[u] = c;
    }else{
      if(col[u] == c) return;
      flag = true;
      return;
    }
    if(flag) return;
    for(auto v: E[u]){
      dfs(v, c^1);
    }
  };
  for(int i = 0 ; i < (int) e.size(); ++i){
    if(col[i] == -1){
      dfs(i, 0);
    }
  }
  if(flag){
    cout<<"NO\n"; 
  }else{
    cout<<"YES\n";
  }

}
int main(){
  int _ = 1;
  cin>>_;
  while(_--){
    solve();
  }
}

C++(g++ 7.5.0) 解法, 执行用时: 37ms, 内存消耗: 480K, 提交时间: 2022-09-26 22:46:06

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 10010;

struct Edge {
    int u, v;
} edges[M];
int v[N], id[N];
int p[N * 6];
int n, m;

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

bool check(int i, int j) {
    int a = id[edges[i].u], b = id[edges[i].v];
    int c = id[edges[j].u], d = id[edges[j].v];
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    if (b > c && b < d && a < c) return true;
    if (d > a && d < b && c < a) return true;
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        auto& [u, v] = edges[i];
        cin >> u >> v;
    } 
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        id[v[i]] = i;
    }
    if (m > 3 * n - 6) {
        cout << "NO\n";
        return;
    }
    for (int i = 1; i <= 2 * m; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (check(i, j)) {
                if (find(i) == find(j)) {
                    cout << "NO\n";
                    return;
                }
                p[find(i)] = find(j + m);
                p[find(j)] = find(i + m);
            }
        }
    }
    cout << "YES\n";
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}