ถมดินรวมเกาะ(island)

โจทย์

Disjoined Set Union(DSU) เป็น Algorithm ที่เกี่ยวกับการดำเนินการของเซต(การ Union) ใน DSU มีฟังก์ชันที่สำคัญคือ find_root find_root source (C++) :

int find_root(int u){
    if(parent[u]==u){
        return u;
    }
    parent[u] = find_root(parent[u]);
    return parent[u];
}

ภาษาC++หลายวันคำเสอนคำว่า std::sort เป็นการเรียง Array ไม่ว่าจะเป็นชนิดตัวแปรใดก็ตาม Syntax :

std::sort(array,array+counter);

อยู่ในไลบารี

#include<algorithm>

ในส่วนของการเรียงชุดข้อมูล เช่น

(1,2),(1,4),(2,1),(4,1),(1,5)

จะใช้เป็นการ sort Struct ในส่วนของการ std::sort นั้นจะเรียงแบบน้อยไปมาก ซึ่งการทำให้เรียงจากมากไปน้อยนั้นก็ง่ายๆโดยการใช้

std::sort(array,array+counter,std::greater<int>());

ในการ sort struct นั้นจะคล้ายๆกับการเรียงกลุ่มของข้อมูล Syntax :

bool operator < (const A&o) const{
if(name!=o.name) return o<o.name;
}

ส่วนมากจะเขียนไว้ใน struct ดูได้ตามภาพ

  struct A{
    int x,y;
    bool opeartor < (const A&o) const{
      if(x!=o.x){
        return x < o.x;
      }
      return y < o.y;
    }
  };

จากภาพ เป็นการเรียงจากน้อยไปมาก สามารถเรียงจากมากไปน้อยได้โดยการ เปลี่ยนเครื่องหมาย ตามภาพ

struct A{
    int x,y;
    bool opeartor < (const A&o) const{
      if(x!=o.x){
        return x > o.x;
      }
      return y > o.y;
    }
  };

สวัสดีครับ เว็บไซต์นี้เป็น blog ส่วนตัวของผม blog ในเว็บไซต๋นี้จะมีเนื้อหาเกี่ยวกับ programming และเรื่องทั่วไป เว็บไซต์นี้เป็นเว็บไซต์ที่พัฒนามาจาก Polar