互聯組件

Question

我正確編碼this問題，並使用BFS算法

這裏是我的代碼

#include<iostream> 
#include<vector> 
#include<string.h> 
#include<cstdio> 
#include<queue> 
using namespace std; 

int main() 
{ 
queue<int>q; 
bool visited[100000]; 
int t,i,j,x,y; 
int n,e; 
cin>>t; 
while(t--) 
{ 
scanf("%d%d",&n,&e); 
vector< vector<int> >G(n); 
memset(visited,0,sizeof(visited)); 

for(i=0;i<e;i++) 
{ 
scanf("%d%d",&x,&y); 
G[x].push_back(y); 
G[y].push_back(x); 
} 

int ans=0; 
for(i=0;i<n;i++) 
{ 
if(!visited[i]) 
{ 
q.push(i); 
visited[i]=1; 

while(!q.empty()) 
{ 
int p=q.front(); 
q.pop(); 
for(j=0;j<G[p].size();j++) 
{ 
if(!visited[G[p][j]]) 
{ 
visited[G[p][j]]=1; 
q.push(G[p][j]); 
} 
} 
} 
ans++; 
} 
} 
printf("%d\n",ans); 
} 
} 

在0.39秒獲得接受，但之後我檢查其他認可的代碼在0.15秒 我不不明白他做了什麼。 有些身體請解釋。

我只是明白他沒有使用bfs或dfs算法。 以及爲什麼他的方法在較短的時間內被接受。

這裏是他的代碼

#include <iostream> 
#include <vector> 
#include <stdio.h> 

using namespace std; 

int p[100001]; 


int find(int a) 
{ 
int root = a; 
while (p[a] != a) { 
    a = p[a]; 
} 
while (root != a) { 

    int root2 = p[root]; 
    p[root] = a; 
    root = root2; 
} 

return a; 

}

int main() 
    { 
int t; 

scanf("%d",&t); 
while (t--) { 
    int n,m,a,b,q; 

    scanf("%d%d",&n,&m); 
    for (int i = 0; i < n; i++) 
     p[i] = i; 

    //int count = n; 

    for (int i = 0; i < m;i++) { 

     scanf("%d%d",&a,&b); 
     int root = find(a); 
     int root2 = find(b); 
     p[root2] = root; 

    } 
    int count = 0; 
    for (int i = 0; i < n;i++) { 
     if (p[i] == i) 
      count++; 

    } 
    printf("%d\n",count); 
} 
return 0; 

}

Answer 1

該代碼使用disjoint set forest。一個能夠執行聯合查找的非常有效的數據結構。本質上，用戶具有一組的組，並且可以執行兩個操作：

• 加入兩套
• 支票設置元素屬於

以上也該算法使用一個重要啓發式 - 路徑壓縮。通常不相交的集合是使用一個更多的啓發式實現 - 按等級結合，但作者決定不使用它。