5408 2023. 05. 13 10:28:55 TomaSajt Kritikus munkák cpp17 Hibás válasz 50/100 93ms 28648 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<int> d, l;
set<int> res;

int t = 0;

void dfs(int u) {
  d[u] = l[u] = ++t;
  for (auto &v : g[u]) {
    if (d[v]) {
      l[u] = min(l[u], d[v]);
      continue;
    }
    dfs(v);
    l[u] = min(l[u], l[v]);
    if (l[v] >= d[u]) res.insert(u);
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  g.resize(n + 2), d.resize(n + 2), l.resize(n + 2);
  vector<int> in_deg(n + 1), out_deg(n + 1);
  while (m--) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v), g[v].push_back(u);
    out_deg[u]++, in_deg[v]++;
  }
  for (int i = 1; i <= n; i++) {
    if (in_deg[i] == 0) g[0].push_back(i), g[i].push_back(0);
    if (out_deg[i] == 0) g[n + 1].push_back(i), g[i].push_back(n + 1);
  }
  dfs(0);

  res.erase(0), res.erase(n + 1);
  cout << res.size() << '\n';
  for (auto &r : res) cout << r << ' ';
  return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 57ms 13376 KiB
subtask2 25/25
3 Elfogadva 57ms 13376 KiB
4 Elfogadva 2ms 2128 KiB
5 Elfogadva 3ms 2400 KiB
6 Elfogadva 3ms 2688 KiB
7 Elfogadva 3ms 2684 KiB
8 Elfogadva 4ms 3076 KiB
subtask3 25/25
9 Elfogadva 4ms 3076 KiB
10 Elfogadva 16ms 5664 KiB
11 Elfogadva 8ms 4312 KiB
12 Elfogadva 8ms 4440 KiB
13 Elfogadva 12ms 5120 KiB
14 Elfogadva 12ms 5052 KiB
subtask4 0/25
15 Elfogadva 12ms 5052 KiB
16 Elfogadva 48ms 16236 KiB
17 Hibás válasz 46ms 15272 KiB
18 Hibás válasz 45ms 15472 KiB
19 Hibás válasz 45ms 16180 KiB
20 Hibás válasz 45ms 16464 KiB
subtask5 0/25
21 Hibás válasz 45ms 16464 KiB
22 Hibás válasz 89ms 25868 KiB
23 Hibás válasz 93ms 26312 KiB
24 Hibás válasz 92ms 26364 KiB
25 Hibás válasz 89ms 26968 KiB
26 Hibás válasz 86ms 28648 KiB