Josif_tepe

Untitled

Jan 25th, 2026
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. using namespace std;
  7. const int maxn=1500;
  8.  
  9. int idx[maxn];
  10. int sz[maxn];
  11.  
  12. void init(){
  13.   for(int i=0;i<maxn;i++){
  14.     idx[i]=i;
  15.     sz[i]=1;
  16.   }
  17. }
  18.  
  19. int find_root(int x) {
  20.   while(x!=idx[x]){
  21.     idx[x]=idx[idx[x]];
  22.     x=idx[x];
  23.   }
  24.   return x;
  25. }
  26.  
  27. void union_set(int A,int B){
  28.   int rootA=find_root(A);
  29.   int rootB=find_root(B);
  30.  
  31.   if(rootA!=rootB){
  32.     if(sz[rootA]<sz[rootB]){
  33.         idx[rootA]=idx[rootB];
  34.         sz[rootB]+=sz[rootA];
  35.     }else{
  36.       idx[rootB]=idx[rootA];
  37.       sz[rootA]+=sz[rootB];
  38.     }
  39.   }
  40. }
  41.  
  42. bool check_set(int A,int B){
  43.   return (find_root(A)==find_root(B));
  44. }
  45.  
  46. vector<int>graph[maxn];
  47.  
  48. int main()
  49. {
  50.     init();
  51.  int n;
  52.  cin>>n;
  53.  vector<pair<int ,pair<int,int>>>v;
  54.  for(int i=1;i<n;i++){
  55.     for(int j=i+1;j<=n;j++){
  56.         int x;
  57.         cin>>x;
  58.         v.push_back({x,{i,j}});
  59.     }
  60.  }
  61.    
  62.  sort(v.begin(),v.end());
  63.  for(int i=0;i<v.size();i++){
  64.     int A=v[i].second.first;
  65.     int B=v[i].second.second;
  66.     int w=v[i].first;
  67.     bool c=check_set(A,B);
  68.      if(c==true){
  69.         continue;
  70.     }else{
  71.         union_set(A,B);
  72.         graph[A].push_back(B);
  73.         graph[B].push_back(A);
  74.     }
  75.  }
  76.  
  77.  for(int i=1;i<=n;i++){
  78.      cout << graph[i].size() << " ";
  79.      sort(graph[i].begin(), graph[i].end());
  80.     for(int j=0;j<graph[i].size();j++){
  81.         cout<<graph[i][j]<<" ";
  82.     }
  83.     cout<<endl;
  84.  }
  85.  
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment