54082023-05-13 10:28:55TomaSajtKritikus munkákcpp17Hibás válasz 50/10093ms28648 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Elfogadva57ms13376 KiB
subtask225/25
3Elfogadva57ms13376 KiB
4Elfogadva2ms2128 KiB
5Elfogadva3ms2400 KiB
6Elfogadva3ms2688 KiB
7Elfogadva3ms2684 KiB
8Elfogadva4ms3076 KiB
subtask325/25
9Elfogadva4ms3076 KiB
10Elfogadva16ms5664 KiB
11Elfogadva8ms4312 KiB
12Elfogadva8ms4440 KiB
13Elfogadva12ms5120 KiB
14Elfogadva12ms5052 KiB
subtask40/25
15Elfogadva12ms5052 KiB
16Elfogadva48ms16236 KiB
17Hibás válasz46ms15272 KiB
18Hibás válasz45ms15472 KiB
19Hibás válasz45ms16180 KiB
20Hibás válasz45ms16464 KiB
subtask50/25
21Hibás válasz45ms16464 KiB
22Hibás válasz89ms25868 KiB
23Hibás válasz93ms26312 KiB
24Hibás válasz92ms26364 KiB
25Hibás válasz89ms26968 KiB
26Hibás válasz86ms28648 KiB