QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#777532#2341. Dead-End DetectorwxhtzdyAC ✓353ms81532kbC++202.0kb2024-11-24 02:57:082024-11-24 02:57:16

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 02:57:16]
  • 评测
  • 测评结果:AC
  • 用时:353ms
  • 内存:81532kb
  • [2024-11-24 02:57:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  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);
  }
  vector<pair<int, int>> res;
  vector<bool> skip(n);
  {
    vector<bool> was(n);
    bool ok;
    vector<int> ver;
    function<void(int, int)> Dfs = [&](int v, int pv) {
      ver.push_back(v);
      was[v] = true;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        if (!was[u]) {
          Dfs(u, v);
        } else {
          ok = false;
        }
      }
    };
    for (int i = 0; i < n; i++) {
      if (was[i]) {
        continue;
      }
      ok = true;
      ver.clear();
      Dfs(i, i);
      if (ok) {
        for (int i : ver) {
          skip[i] = true;
          if (int(g[i].size()) == 1) {
            res.emplace_back(i, g[i][0]);
          }
        }
      }
    }
  }
  {
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
      deg[i] = int(g[i].size());
    }
    vector<int> que;
    for (int i = 0; i < n; i++) {
      if (skip[i]) {
        continue;
      }
      if (deg[i] == 1) {
        que.push_back(i);
      }
    }
    for (int b = 0; b < int(que.size()); b++) {
      int i = que[b];
      for (int j : g[i]) {
        deg[j] -= 1;
        if (deg[j] == 1) {
          que.push_back(j);
        }
      }
    }
    vector<int> in(n);
    for (int i : que) {
      in[i] = true;
    }
    for (int i = 0; i < n; i++) {
      if (skip[i] || !in[i]) {
        continue;
      }
      for (int j : g[i]) {
        if (!in[j]) {
          res.emplace_back(j, i);
        }
      }
    }
  }
  cout << int(res.size()) << '\n';
  sort(res.begin(), res.end());
  for (auto& p : res) {
    cout << p.first + 1 << " " << p.second + 1 << '\n';
  }
  return 0;  
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3604kb

Test #3:

score: 0
Accepted
time: 162ms
memory: 81456kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 3604kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3548kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3760kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 3608kb

Test #8:

score: 0
Accepted
time: 5ms
memory: 18832kb

Test #9:

score: 0
Accepted
time: 1ms
memory: 3612kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3624kb

Test #11:

score: 0
Accepted
time: 1ms
memory: 3756kb

Test #12:

score: 0
Accepted
time: 1ms
memory: 3832kb

Test #13:

score: 0
Accepted
time: 44ms
memory: 7320kb

Test #14:

score: 0
Accepted
time: 49ms
memory: 7848kb

Test #15:

score: 0
Accepted
time: 222ms
memory: 36544kb

Test #16:

score: 0
Accepted
time: 207ms
memory: 40452kb

Test #17:

score: 0
Accepted
time: 223ms
memory: 45992kb

Test #18:

score: 0
Accepted
time: 214ms
memory: 44672kb

Test #19:

score: 0
Accepted
time: 1ms
memory: 3844kb

Test #20:

score: 0
Accepted
time: 1ms
memory: 3644kb

Test #21:

score: 0
Accepted
time: 1ms
memory: 3832kb

Test #22:

score: 0
Accepted
time: 64ms
memory: 13808kb

Test #23:

score: 0
Accepted
time: 246ms
memory: 62780kb

Test #24:

score: 0
Accepted
time: 96ms
memory: 81532kb

Test #25:

score: 0
Accepted
time: 256ms
memory: 79028kb

Test #26:

score: 0
Accepted
time: 92ms
memory: 81376kb

Test #27:

score: 0
Accepted
time: 240ms
memory: 81456kb

Test #28:

score: 0
Accepted
time: 264ms
memory: 81508kb

Test #29:

score: 0
Accepted
time: 245ms
memory: 81448kb

Test #30:

score: 0
Accepted
time: 100ms
memory: 38328kb

Test #31:

score: 0
Accepted
time: 165ms
memory: 38496kb

Test #32:

score: 0
Accepted
time: 103ms
memory: 40360kb

Test #33:

score: 0
Accepted
time: 206ms
memory: 40424kb

Test #34:

score: 0
Accepted
time: 353ms
memory: 75956kb

Test #35:

score: 0
Accepted
time: 229ms
memory: 37096kb

Test #36:

score: 0
Accepted
time: 254ms
memory: 43416kb

Test #37:

score: 0
Accepted
time: 244ms
memory: 52352kb

Test #38:

score: 0
Accepted
time: 235ms
memory: 37212kb

Test #39:

score: 0
Accepted
time: 212ms
memory: 36736kb

Test #40:

score: 0
Accepted
time: 223ms
memory: 47868kb

Test #41:

score: 0
Accepted
time: 221ms
memory: 37104kb

Test #42:

score: 0
Accepted
time: 249ms
memory: 35296kb

Test #43:

score: 0
Accepted
time: 220ms
memory: 36032kb

Test #44:

score: 0
Accepted
time: 200ms
memory: 45264kb

Test #45:

score: 0
Accepted
time: 191ms
memory: 45352kb