fork download
copy 
  1. // 506 D
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <map>
  5. #include <unordered_map>
  6. #define ee '\n'
  7. int n, m;
  8. struct DisjointSet {
  9.     std::unordered_map<int, int> p;
  10.     std::unordered_map<int, int> Rank;
  11.     int Find(int x) {
  12.         if(!p.count(x)) {
  13.             //printf("not create yet!\n");
  14.             Rank[x] = 1;
  15.             p[x] = x;
  16.             return x;
  17.         }
  18.         //printf("go to %d", p[x]);
  19.         p[x] = (x == p[x] ? x : Find(p[x]));
  20.         return p[x];
  21.     }
  22.     void Union(int x, int y) {
  23.         int px = Find(x), py = Find(y);
  24.         int rx = Rank[x], ry = Rank[y];
  25.         if(rx < ry) p[px] = py;
  26.         else if(rx > ry) p[py] = px;
  27.         else {
  28.             p[px] = py;
  29.             Rank[y]++;
  30.         }
  31.     }
  32. };
  33.  
  34. int main() {
  35.     scanf("%d %d", &n, &m);
  36.     std::map<int, DisjointSet> djs;
  37.     for(int i = 0; i < m; i++) {
  38.         int a, b, c;
  39.         scanf("%d %d %d", &a, &b, &c);
  40.         djs[c].Union(a, b);
  41.     }
  42.     int q; scanf("%d", &q);
  43.     while(q--) {
  44.         int a, b; scanf("%d %d", &a, &b);
  45.         long long ans = 0;
  46.         for(std::map<int, DisjointSet>::iterator iter = djs.begin(); iter != djs.end(); iter++) {
  47.             if(iter->second.Find(a) == iter->second.Find(b)) ans++;
  48.         }
  49.         printf("%lld\n", ans);
  50.     }
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A59vYM
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!