查找不相交集合的數量

對於不熟悉不相交集合數據結構的人員。查找不相交集合的數量

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

我試圖找到沒有。來自特定朋友的朋友羣體及其關係。當然，毫無疑問，這可以使用BFS/DFS輕鬆實現。但是我選擇使用不相交集合，我也傾向於找到該人屬於的朋友組等等，並且在這種情況下，脫節設置聽起來是合適的。

我已經實現了不相交集數據結構，現在我需要找到它包含的不相交集的數目（這會給我組的數量）。

現在，我被困在執行上如何有效地找到相交集合的號，作爲朋友的數量可以大到1 00 00 0

選項，我認爲應該工作。

將新套裝附在原件的後面，銷燬舊套件。
更改他們在每個工會的每個元素的父母。

但由於朋友的數量是巨大的，我不知道這是正確的做法，也許，如果有任何其他有效的方式還是應該繼續和實施上述任何。

這裏是我的其他詳細信息的代碼。（I'have沒有實現計數不相交集在這裏）

//disjoint set concept 

//https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/ 
// initially all the vertices are takes as single set and they are their own representative. 
// next we see, compare two vertices, if they have same parent(representative of the set), we leave it. 
// if they don't we merge them it one set. 
// finally we get different disjoint sets. 

#includes ... 
using namespace std; 

#define edge pair<int, int> 
const int max 1000000; 
vector<pair<int, edge > > graph, mst; 
int N, M; 
int parent[max]; 

int findset(int x, int* parent){ 
//find the set representative. 
    if(x != parent[x]){ 
     parent[x] = findset(parent[x], parent); 
    } 

    return parent[x]; 
} 
void disjoints(){ 
    for(int i=0; i<M; i++){ 
     int pu = findset(graph[i].second.first, parent); 
     int pv = findset(graph[i].second.second, parent); 

     if(pu != pv){ //if not in the same set. 
      mst.push_back(graph[i]); 
      total += graph[i].first; 
      parent[pu] = parent[pv]; // create the link between these two sets 
     } 
    } 
} 
void noOfDisjoints(){ 
    //returns the No. of disjoint set. 
} 
void reset(){ 
    for(int i=0; i<N; i++){ 
     parent[i] = i; 
    } 
} 

int main() { 
      cin>>N>>M; // No. of friends and M edges 
     int u,v,w; // u= source, v= destination, w= weight(of no use here). 
     reset(); 
     for(int i =0; i<M ;i++){ 
      cin>>u>>v>>w; 
      graph.push_back(pair<int, edge>(w,edge(u,v))); 
     } 
     disjoints(); 
     print(); 
    return 0; 
}

來源

2015-06-17 nitte93user3232918

在分離集數據結構上的兩個項目a,b每個工會operaiton有兩種可能的情況：

您試圖團結從同一組項目。在這種情況下，什麼都不做，並且不相交集合的數量保持不變。
您將來自兩個不同集合的項目合併在一起，因此您基本上可以將兩個集合合併爲一個 - 將不相交集合的數量有效地減少一個。

由此我們可以得出結論，通過跟蹤上述類型（2）的聯合數量，很容易在每個時刻找到不相交集合的數目。
如果我們用succ_unions表示這個數字，那麼每個點的集合總數爲number_of_initial_sets - succ_unions。

來源

2015-06-17 22:05:17 amit

啊，經驗教訓，不要過時，謝謝。 – nitte93user3232918

@ user3232918你是最受歡迎的。很高興我能幫上忙。 – amit

如果你需要知道的是不相交集數量而不是他的是，一種選擇是將一個計數器變量添加到您的數據結構中，並計算出有多少不相交的集合。最初，它們有n，每個元素一個。每次執行聯合操作時，如果這兩個元素沒有相同的代表，那麼您知道您正在將兩個不相交的集合合併爲一個，因此您可以遞減計數器。這看起來像這樣：

if (pu != pv){ //if not in the same set. 
    numDisjointSets--; // <--- Add thie line 
    mst.push_back(graph[i]); 
    total += graph[i].first; 
    parent[pu] = parent[pv]; // create the link between these two sets 
}

希望這有助於！

來源

2015-06-17 22:04:30 templatetypedef

我希望我能接受兩個答案。可悲的是，我不能。謝謝 – nitte93user3232918

查找不相交集合的數量

回答

相關問題