fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Edge {
  8.     int u, v, w, id;
  9. };
  10.  
  11. struct DSU {
  12.     vector<int> parent;
  13.     DSU(int n) {
  14.         parent.resize(n + 1);
  15.         for (int i = 1; i <= n; ++i) parent[i] = i;
  16.     }
  17.     int find(int i) {
  18.         if (parent[i] == i) return i;
  19.         return parent[i] = find(parent[i]);
  20.     }
  21.     void unite(int i, int j) {
  22.         int root_i = find(i);
  23.         int root_j = find(j);
  24.         if (root_i != root_j) parent[root_i] = root_j;
  25.     }
  26. };
  27.  
  28. bool compareEdges(const Edge& a, const Edge& b) {
  29.     return a.w < b.w;
  30. }
  31.  
  32. int main() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.  
  36.     int n, m;
  37.     if (!(cin >> n >> m)) return 0;
  38.  
  39.     vector<Edge> edges(m);
  40.     for (int i = 0; i < m; ++i) {
  41.         cin >> edges[i].u >> edges[i].v >> edges[i].w;
  42.         edges[i].id = i;
  43.     }
  44.  
  45.     vector<Edge> sorted_edges = edges;
  46.     sort(sorted_edges.begin(), sorted_edges.end(), compareEdges);
  47.  
  48.     vector<bool> result(m);
  49.     DSU dsu(n);
  50.  
  51.     int i = 0;
  52.     while (i < m) {
  53.         int j = i;
  54.         while (j < m && sorted_edges[j].w == sorted_edges[i].w) {
  55.             if (dsu.find(sorted_edges[j].u) != dsu.find(sorted_edges[j].v)) {
  56.                 result[sorted_edges[j].id] = true;
  57.             } else {
  58.                 result[sorted_edges[j].id] = false;
  59.             }
  60.             j++;
  61.         }
  62.  
  63.         j = i;
  64.         while (j < m && sorted_edges[j].w == sorted_edges[i].w) {
  65.             dsu.unite(sorted_edges[j].u, sorted_edges[j].v);
  66.             j++;
  67.         }
  68.         i = j;
  69.     }
  70.  
  71.     for (int k = 0; k < m; ++k) {
  72.         if (result[k]) cout << "TAK\n";
  73.         else cout << "NIE\n";
  74.     }
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6 10
1 2 2
1 6 1
1 5 3
4 1 5
2 6 2
2 3 5
4 3 4
3 5 4
4 5 4
5 6 3
stdout
copy 
TAK
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
TAK
https://ideone.com/VsaeTa
language:
C++14 (gcc 8.3)
created:
1 hour 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!