fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int N, M, K;
  9.     if (!(cin >> N >> M >> K)) return 0;
  10.     vector<vector<pair<int,int>>> adj(N+1);
  11.     vector<pair<int,int>> edges(M+1);
  12.     for (int i = 1; i <= M; ++i) {
  13.         int u, v;
  14.         cin >> u >> v;
  15.         edges[i] = {u, v};
  16.         adj[u].push_back({v, i});
  17.         adj[v].push_back({u, i});
  18.     }
  19.  
  20.     vector<int> vis(N+1, 0);
  21.     function<void(int)> dfs_conn = [&](int u){
  22.         vis[u] = 1;
  23.         for (auto pr: adj[u]) {
  24.             int v = pr.first;
  25.             if (!vis[v]) dfs_conn(v);
  26.         }
  27.     };
  28.     dfs_conn(1);
  29.     for (int i = 1; i <= N; ++i) {
  30.         if (!vis[i]) {
  31.             cout << -1 << '\n';
  32.             return 0;
  33.         }
  34.     }
  35.  
  36.     vector<int> tin(N+1, 0), low(N+1, 0);
  37.     int timer = 0;
  38.     bool hasBridge = false;
  39.     function<void(int,int)> dfs = [&](int u, int pe) {
  40.         tin[u] = low[u] = ++timer;
  41.         for (auto pr : adj[u]) {
  42.             int v = pr.first, id = pr.second;
  43.             if (id == pe) continue;
  44.             if (!tin[v]) {
  45.                 dfs(v, id);
  46.                 low[u] = min(low[u], low[v]);
  47.                 if (low[v] > tin[u]) {
  48.                     hasBridge = true;
  49.                 }
  50.             } else {
  51.                 low[u] = min(low[u], tin[v]);
  52.             }
  53.             if (hasBridge) return;
  54.         }
  55.     };
  56.     dfs(1, -1);
  57.  
  58.     if (hasBridge) {
  59.         cout << -1 << '\n';
  60.         return 0;
  61.     }
  62.  
  63.     int C = M - (N - 1);
  64.     if (C <= 0) { 
  65.         cout << -1 << '\n';
  66.         return 0;
  67.     }
  68.     int perDay = min(K, C);
  69.     int days = (M + perDay - 1) / perDay;
  70.     cout << days << '\n';
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/omrA4R
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!