fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define TASK "FILE"
  4.  
  5. #define ll long long
  6. #define endl '\n'
  7. #define el cout << '\n'
  8. #define pii pair<int, int>
  9. #define pll pair<ll, ll>
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define SZ(v) (int)((v).size()) 
  14. #define ms(A, n) memset((A), (n), sizeof((A)))
  15. #define ALL(v) (v).begin(), (v).end()
  16. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  17. #define FORD(i, a, b) for(int i = (a); i >= (b); i--)
  18. #define FORX(x, v) for(auto x : (v))
  19.  
  20. #define MASK(x) (1 << (x))
  21. #define BIT(i, x) (((x) >> (i)) & 1)
  22. #define _TANHNV_ signed main()
  23.  
  24. template <class X, class Y>
  25. bool maximize(X &x, const Y &y){
  26.     return (x < y) ? (x = y), 1 : 0; 
  27. }
  28. template <class X, class Y>
  29. bool minimize(X &x, const Y &y){
  30.     return (x > y) ? (x = y), 1 : 0; 
  31. }
  32.  
  33. const int maxn = 1e6 + 5;
  34. const ll MOD = 1e9 + 7;
  35. const int inf = 2e9;
  36. const ll INF = 2e18;
  37. const int LOG = 19;
  38.  
  39. /* END OF TEMPLATE */
  40.  
  41. int n, m;
  42. vector<pii> adj[maxn];
  43. struct edge{int u, v, id;};
  44. pii canh[maxn];
  45. vector<pii> Amst[maxn];
  46. bool in[maxn];
  47. int h[maxn];
  48. pii par[maxn];
  49. int ans[maxn];
  50.  
  51. struct DSU{
  52.     int n;
  53.     vector<int> root;
  54.     void init(int _n = 0){
  55.         n = _n;
  56.         root.assign(n + 2, 0);
  57.         FOR(u, 1, n){
  58.             root[u] = u;
  59.         }
  60.     }
  61.  
  62.     int getRoot(int u){return (u == root[u]) ? u : root[u] = getRoot(root[u]);}
  63.  
  64.     bool unite(int u, int v){
  65.         u = getRoot(u);
  66.         v = getRoot(v);
  67.         if(u == v) return 0;
  68.         if(h[u] > h[v]) swap(u, v);
  69.         root[v] = u;
  70.         return 1;
  71.     }
  72. } dsu;
  73.  
  74. void dfs(int u, int p){
  75.     FORX(e, Amst[u]){
  76.         int v = e.fi, id = e.se;
  77.         if(v == p) continue;
  78.         h[v] = h[u] + 1;
  79.         par[v] = {u, id};
  80.         dfs(v, u);
  81.     }
  82. }
  83.  
  84. void inp(){
  85.     cin >> n >> m;
  86.     FOR(i, 1, m){
  87.         int u, v; cin >> u >> v;
  88.         if(u > v) swap(u, v);
  89.         canh[i] = {u, v};
  90.     }
  91. }
  92.  
  93. void sol(){
  94.     dsu.init(n);
  95.     FOR(id, 1, m){
  96.         int u = canh[id].fi, v = canh[id].se;
  97.         if(dsu.unite(u, v)){
  98.             in[id] = 1;
  99.             Amst[u].pb({v, id});
  100.             Amst[v].pb({u, id});
  101.         }
  102.     }
  103.     dfs(1, 1);
  104.  
  105.     DSU cc;
  106.     cc.init(n);
  107.     FOR(id, 1, m){
  108.         int u = canh[id].fi, v = canh[id].se;
  109.         if(!in[id]){
  110.             ans[id] = id;
  111.             int ru = cc.getRoot(u), rv = cc.getRoot(v);
  112.             while(ru != rv){
  113.                 if(h[ru] > h[rv]) swap(ru, rv);
  114.                 cc.unite(par[rv].fi, rv);
  115.                 ans[par[rv].se] = id;
  116.                 rv = cc.getRoot(rv);
  117.             }
  118.         }
  119.     }
  120.  
  121.     FOR(i, 1, m) cout << ((ans[i] == 0) ? -1 : ans[i]) << " ";
  122. }
  123.  
  124. _TANHNV_{
  125.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  126.     if(fopen(TASK".inp", "r")){
  127.         freopen(TASK".inp", "r", stdin);
  128.         freopen(TASK".out", "w", stdout);
  129.     }
  130.     inp();
  131.     sol();
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0.02s 55372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kUagMq
language:
C++14 (gcc 8.3)
created:
3 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!