0
I 그래프에 연합 찾기 수행하는 코드를 작성하고 최대 및 최소 크기 방법 :
nm의 [N 노드의 수이고, m은 I는 각각의 에지가 발생할 때 두 노드입력의 첫 줄이 <br/></p> <p>이산 집합
접속되어 있는지를 나타내는 에지의 수]
그럼 m 라인을 따라는, I는 노드를 연결하기 위해, 연합 동작을 수행한다. 노조를 수행 한 후, 나는 또한 최소 크기의 부분 집합을 얻기 위해 무차별를 사용하고있는 가장 큰 부분 집합의 크기와이 지금까지 내 코드입니다
작은 부분 집합,
#include <iostream>
using namespace std;
int arr[100001];
int size[100001];
void initialize(int n){
for(int i=1; i<=n; i++){
arr[i] = i;
size[i] = 1;
}
}
int root(int a){
while(arr[a] != a){
//Path compression
arr[a] = arr[arr[a]];
a = arr[a];
}
return a;
}
void weighted_union(int a, int b){
int root_a = root(a);
int root_b = root(b);
//Perform union, if the two elements are not already in the same subset
if(root(a) != root(b)){
if(size[root_a] < size[root_b]){
arr[root_a] = root_b;
size[root_b] += size[root_a];
}
else{
arr[root_b] = root_a;
size[root_a] += size[root_b];
}
}
}
void print_result(int n){
int max_size = 1;
int min_size = 100000;
for(int i=1; i<=n; i++){
//If it's a root node, then check the size
if(arr[i] == i){
if(size[i] > max_size){
max_size = size[i];
}
if(size[i] < min_size){
min_size = size[i];
}
}
}
cout<<max_size - min_size<<endl;
}
int main() {
//For fast IO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,a,b;
cin>>n>>m;
initialize(n);
for(int edge=0; edge<m; edge++){
cin>>a>>b;
weighted_union(a,b);
print_result(n);
}
return 0;
}
을 알고 싶어요 및 최대 크기 서브 세트. 이 코드는 Sphere Online Judge에서 시간 초과되었습니다.
최소 크기의 하위 집합과 최대 크기의 하위 집합을 가져 오는보다 효율적인 방법은 무엇입니까?
SPOJ 질문 링크는 다음과 같습니다 끊긴 세트를 사용 http://www.spoj.com/problems/LOSTNSURVIVED/