fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define F first
  4. #define S second
  5. #define forn(i, n) for(int i = 0; i < int(n); i++)
  6. #define p_b push_back
  7. #define all(c)              c.begin(), c.end()
  8. using namespace std;
  9. typedef long long ll; //printf("%lld ", ll); to out put long
  10. typedef pair <int , int> pii;
  11. typedef pair <ll , ll> pll;
  12. const double eps = 1e-6;
  13. const int MAXN = 1e5 + 5;
  14. const ll MOD = 1e9 + 7;
  15. bool ODD(ll O) {return (O % 2 != 0);}
  16. ll gcd(ll a, ll b) {return __gcd(a , b);}
  17. ll lcm(ll a, ll b) {return a * b / gcd(a , b);}
  18. int dx[] = {1, 0, -1 ,0 , -1 , 0};
  19. int dy[] = {0, 1, 0, -1 , -1 , 0};
  20. ll power (ll x, ll y) {
  21.     if(y == 0) return 1;
  22.     if(ODD(y)) return (x * power(x , y / 2) * power(x , y / 2));
  23.     return (power(x , y / 2) * power(x , y / 2));
  24. }
  25. /*------ never give up --------*/
  26.  
  27. vector < vector <int>  > adj;
  28. vector <bool> vis, in_stack;
  29. stack <int> st;
  30. map <pii , bool> mp;
  31. vector <pair <pii , int> > vc;
  32. int rm = 0;
  33. void dfs(int node) {
  34.     if(rm <= 0) return;
  35.     if(vis[node]) {
  36.         if(in_stack[node]) {
  37.             int x1 = -1, x2 = -1, x3 = st.top();
  38.             while(x1 != node) {
  39.                 x1 = st.top();
  40.                 st.pop();
  41.                 if(st.empty()) break;
  42.                 if(st.top() == node) {
  43.                     x2 = st.top();
  44.                     mp[{x2 , x1}] = 1;
  45.                     --rm;
  46.                     if(rm <= 0) return;
  47.                     break;
  48.                 }
  49.                 x2 = st.top();
  50.                 mp[{x2 , x1}] = 1;
  51.                 in_stack[x1] = 0;
  52.                 --rm;
  53.                 if(rm <= 0) return;
  54.             }
  55.             mp[{node , x3}] = 1;
  56.             in_stack[node] = 1;
  57.  
  58.  
  59.         } else return;
  60.     }
  61.     vis[node] = in_stack[node] = 1;
  62.     st.push(node);
  63.     for(int ch : adj[node]) {
  64.         if(mp[{node , ch}]) continue;
  65.         dfs(ch);
  66.     }
  67. }
  68. void solve(int n , int k , int m) {
  69.     vis.resize(n + 5 , 0);
  70.     in_stack.resize(n + 5 , 0);
  71.     rm = k - m;
  72.     dfs(0);
  73.     cout << n << "\n";
  74.     for(int i = 0; i < m && k > 0; i++) {
  75.         if(!mp[{vc[i].first.F , vc[i].first.S}]) {
  76.             cout << vc[i].second + 1 << "\n";
  77.             --k;
  78.         }
  79.     }
  80. }
  81. int main () {
  82.     int t = 1;
  83.     //scanf("%d", &t);
  84.     int n, m, k;
  85.     while(t--) {
  86.         cin >> n >> m >> k;
  87.         adj.resize(n + 5);
  88.         for(int i = 0; i < m; i++) {
  89.             int u, v;
  90.             cin >> u >> v;
  91.             u--, v--;
  92.             adj[u].push_back(v);
  93.             vc.push_back({{u , v} , i});
  94.         }
  95.         solve(n , k , m);
  96.     }
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/yB1W29
language:
C++ (gcc 8.3)
created:
3 years 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!