Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <set>
- #include <cstring>
- using namespace std;
- using namespace std;
- vector<int>graph[2000];
- int idx[2000];
- struct node{
- int a;
- int b;
- int distance;
- node(int _a, int _b, int _distance){
- a = _a;
- b = _b;
- distance = _distance;
- }
- bool operator < (const node &tmp)const{
- return distance < tmp.distance;
- }
- };
- int find_root(int a){
- while(idx[a]!=a){
- idx[a]=idx[idx[a]];
- a=idx[a];
- }
- return a;
- }
- bool check(int a, int b){
- if(find_root(a)!=find_root(b)){
- return false;
- }
- else{
- return true;
- }
- }
- void unite_two_elements(int a, int b){
- int _a=find_root(a);
- int _b=find_root(b);
- if(check(a, b)==false){
- idx[_a]=_b;
- }
- }
- int main()
- {
- for(int i=0; i<2000; i++){
- idx[i]=i;
- }
- int n;
- cin>>n;
- vector<node>v;
- for(int i=0; i<n; i++){
- for(int j=i+1; j<n; j++){
- int a;
- cin>>a;
- v.push_back(node(i, j, a));
- }
- }
- sort(v.begin(), v.end());
- for(int i=0; i<v.size(); i++){
- int a=v[i].a;
- int b=v[i].b;
- int d=v[i].distance;
- if(check(a, b)==false){
- unite_two_elements(a, b);
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- }
- for(int i=0; i<n; i++){
- cout<<(int) graph[i].size() << " ";
- sort(graph[i].begin(), graph[i].end());
- for(int j=0; j<graph[i].size(); j++){
- cout<<graph[i][j] + 1<< " ";
- }
- cout<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement