Advertisement
Josif_tepe

Untitled

Jan 23rd, 2023
876
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <set>
  6. #include <cstring>
  7. using namespace std;
  8.  
  9.  
  10. using namespace std;
  11. vector<int>graph[2000];
  12. int idx[2000];
  13. struct node{
  14. int a;
  15. int b;
  16. int distance;
  17. node(int _a, int _b, int _distance){
  18.     a = _a;
  19.     b = _b;
  20.     distance = _distance;
  21. }
  22. bool operator < (const node &tmp)const{
  23. return distance < tmp.distance;
  24. }
  25. };
  26.  
  27. int find_root(int a){
  28. while(idx[a]!=a){
  29.     idx[a]=idx[idx[a]];
  30.     a=idx[a];
  31. }
  32. return a;
  33. }
  34.  
  35.  
  36. bool check(int a, int b){
  37. if(find_root(a)!=find_root(b)){
  38.     return false;
  39. }
  40. else{
  41.     return true;
  42. }
  43. }
  44.  
  45. void unite_two_elements(int a, int b){
  46. int _a=find_root(a);
  47. int _b=find_root(b);
  48. if(check(a, b)==false){
  49. idx[_a]=_b;
  50. }
  51. }
  52.  
  53.  
  54. int main()
  55. {
  56.     for(int i=0; i<2000; i++){
  57.     idx[i]=i;
  58.     }
  59.     int n;
  60.     cin>>n;
  61.     vector<node>v;
  62.  
  63.     for(int i=0; i<n; i++){
  64.         for(int j=i+1; j<n; j++){
  65.             int a;
  66.             cin>>a;
  67.             v.push_back(node(i, j, a));
  68.         }
  69.     }
  70.  
  71.     sort(v.begin(), v.end());
  72.     for(int i=0; i<v.size(); i++){
  73.     int a=v[i].a;
  74.     int b=v[i].b;
  75.     int d=v[i].distance;
  76.     if(check(a, b)==false){
  77.         unite_two_elements(a, b);
  78.         graph[a].push_back(b);
  79.         graph[b].push_back(a);
  80.     }
  81.     }
  82.     for(int i=0; i<n; i++){
  83.         cout<<(int) graph[i].size() << " ";
  84.         sort(graph[i].begin(),   graph[i].end());
  85.         for(int j=0; j<graph[i].size(); j++){
  86.             cout<<graph[i][j] + 1<< " ";
  87.         }
  88.         cout<<endl;
  89.     }
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement