Submission #975079

#	Time	Username	Problem	Language	Result	Execution time	Memory
975079		duckindog	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	39 ms	10580 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 10;
int n, m;
vector<int> ad[N];
bool mk[N][N];
int used[N][N], trace[N][N];

void dfs(int u, int v, int p = 0) { 
  used[u][v] = 1;
  trace[u][v] = p;
  for (const auto& x : ad[v]) { 
    if (mk[u][x]) continue;
    if (used[v][x] == 1) {
      while (v != x) { 
        cout << v << " ";
        tie(u, v) = make_pair(trace[u][v], u);
      }
      cout << x << "\n";
      exit(0);
    } else if (!used[v][x]) dfs(v, x, u);
  }
  used[u][v] = 2;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
    mk[u][v] = mk[v][u] = true;
  }
  for (int i = 1; i <= n; ++i) mk[i][i] = true;

  for (int u = 1; u <= n; ++u) {
    for (int v = u + 1; v <= n; ++v) if (mk[u][v] && !used[u][v]) dfs(u, v);
  }

  cout << "no" << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10