#kruskal's algorithm

[avhumboldt]

Union-Find를 이용한 Kruskal’s Algorithm 구현

#include <iostream> using namespace std;

struct Edge {    int A;    int B;    int C; }; struct Edge *edge; int v,e,*root,*_rank; void quicksort(Edge a[], int first, int end) {   // edge들을 가중치 오름차순으로 정렬    int i=first, j=end;    Edge h;    int x = a[(first+end)/2].C;

   do {        while(a[i].C<x) i++;        while(a[j].C>x) j--;        if(i<=j) {            h=a[i];            a[i]=a[j];            a[j]=h;            i++;            j--;        }    } while(i<=j);    if(first<end) quicksort(a,first,j);    if(i<end) quicksort(a,i,end); }

int _find(int x) { if(root[x] == x) return x; // path compression return root[x] = _find(root[x]); } void _union(int x,int y) { int x_root = _find(x); int y_root = _find(y); if( x_root == y_root) return ;

// union_by-rank if(_rank[x_root] < _rank[y_root]) root[x_root] = y_root; else { root[y_root] = x_root; if(_rank[x_root] == _rank[y_root]) _rank[x_root]++; } } bool _check_graph(int x,int y) { if(_find(x) == _find(y)) return false; return true; } int _kruskal() { int i,weight=0; for(i=0;i<e;i++) { if(_check_graph(edge[i].A,edge[i].B)) { _union(edge[i].A,edge[i].B); weight+=edge[i].C; } } return weight; }

int main() { int i; cin >> v >> e; edge = new Edge[e]; root = new int[v+1]; _rank = new int[v+1]; for(i=1;i<=v;i++) root[i]=i,_rank[i]=0; for(i=0;i<e;i++) { cin >> edge[i].A >> edge[i].B >> edge[i].C; if(edge[i].A > edge[i].B) { int temp; temp=edge[i].A; edge[i].A = edge[i].B; edge[i].B = temp; } } quicksort(edge,0,e-1); cout << _kruskal() << endl; delete [] edge; delete [] root; delete [] _rank; }

vertax : max-10000 , edge: max-100000

memory : 2656KB , time : 148MS

[avhumboldt]

C++ vector를 이용하여 구현한 Kruskal’s Algorithm (time limit)

#include <iostream> #include <vector> using namespace std;

struct Edge { int A; int B; int C; }; vector<pair<int,int>> *vertax; struct Edge *edge; int v,e; bool check_flag=0;

void quicksort(Edge a[], int first, int end) { // edge들을 가중치 오름차순으로 정렬 int i=first, j=end; Edge h; int x = a[(first+end)/2].C;

do { while(a[i].C<x) i++; while(a[j].C>x) j--; if(i<=j) { h=a[i]; a[i]=a[j]; a[j]=h; i++; j--; } } while(i<=j); if(first<end) quicksort(a,first,j); if(i<end) quicksort(a,i,end); } int check_graph(int start,int now_edge, int pr_edge) { int check_count=0; if(now_edge == start) { check_flag=true; return 1; } if(check_flag==true) return 1; int i; for(i=1;i<=vertax[now_edge].size();i++) { if(vertax[now_edge].at(i-1).first!=pr_edge) { check_count += check_graph(start,vertax[now_edge].at(i-1).first,now_edge); } } return check_count;

} int kruskal() { int i,j,weight=0; for(i=0;i<e;i++) { pair<int,int> con1,con2; con1.first = edge[i].B; con1.second = edge[i].C; con2.first = edge[i].A; con2.second = edge[i].C; vertax[edge[i].A].push_back(con1); vertax[edge[i].B].push_back(con2); if(check_graph(edge[i].A,edge[i].B,edge[i].A)>0) { vertax[edge[i].A].pop_back(); vertax[edge[i].B].pop_back(); } else { weight += edge[i].C; } check_flag = false; } return weight; }

int main() { int result; cin >> v >> e; vertax = new vector<pair<int,int>>[v+1]; edge = new struct Edge[e]; for(int i=0;i<e;i++) { cin >> edge[i].A >> edge[i].B >> edge[i].C; } quicksort(edge,0,e-1); result = kruskal(); cout << result << endl; delete [] vertax; delete [] edge; }