minimum cost tree

ViewController.mm

//
//  ViewController.mm
//  minimunCostTree
//
//  Created by MizushimaYusuke on 8/17/15.
//  Copyright (c) 2015 MizushimaYusuke. All rights reserved.
//

#import "ViewController.h"

#include <vector>
#include <memory>
using namespace std;
#define M_MAX 100
class DisjSet {
private:
    int parent[M_MAX];
    int rank[M_MAX];
    
public:
    DisjSet(int n) {
        for (int i=0; i<n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    void mergeSet(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (rank[px] > rank[py]) parent[py] = px;
        else parent[px] = py;
        if (rank[px] == rank[py]) rank[py] = rank[py] + 1;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

typedef struct {int u, v, cost;} Edge;

class KruskalSolver {
private:
    void notify(Edge e) {
        [[NSNotificationCenter defaultCenter] postNotificationName:@"my message" object:[NSValue value:&e withObjCType:@encode(Edge)]];
    }
public:
    int solve(vector<Edge> es, int v) {
        sort(es.begin(), es.end(), [](const Edge &a, const Edge &b) {
            return a.cost < b.cost;
        });
        DisjSet uf (v);
        int cost = 0;
        for (int i=0; i<es.size(); i++) {
            Edge e = es[i];
            if (!uf.same(e.u, e.v)) {
                uf.mergeSet(e.u, e.v);
                cost += e.cost;
                notify(e);
            }
        }
        return cost;
    }
};


@interface ViewController () {
    vector<Edge> edges;
    int count;
}
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    CGPoint pts[] = {
        CGPointMake(80, 150),
        CGPointMake(300, 150),
        CGPointMake(80, 300),
        CGPointMake(300, 300),
        CGPointMake(80, 450)
    };
    
    for (int i=0; i<5; i++) {
        UILabel *v = [[UILabel alloc] initWithFrame:CGRectMake(0, 0, 40, 40)];
        v.tag = i + 1;
        v.textAlignment = NSTextAlignmentCenter;
        v.text = [NSString stringWithFormat:@"%d", i + 1];
        v.textColor = [UIColor whiteColor];
        v.backgroundColor = [UIColor purpleColor];
        v.center = pts[i];
        v.layer.zPosition = 10;
        [self.view addSubview:v];
    }
    
    edges.emplace_back(Edge{0, 1, -80});
    edges.emplace_back(Edge{0, 2, -20});
    edges.emplace_back(Edge{1, 2, -50});
    edges.emplace_back(Edge{1, 3, -10});
    edges.emplace_back(Edge{2, 3, -100});
    edges.emplace_back(Edge{2, 4, -30});
    edges.emplace_back(Edge{3, 4, -20});
    
    for (auto &e : edges) {
        UIView *u = [self.view viewWithTag:e.u + 1];
        UIView *v = [self.view viewWithTag:e.v + 1];
        UIBezierPath *path = [UIBezierPath bezierPath];
        [path moveToPoint:u.center];
        [path addLineToPoint:v.center];
        CAShapeLayer *line = [CAShapeLayer layer];
        line.path = path.CGPath;
        line.lineWidth = 2;
        line.strokeColor = [UIColor purpleColor].CGColor;
        line.fillColor = [UIColor clearColor].CGColor;
        [self.view.layer addSublayer:line];
        
        UILabel *costLabel = [[UILabel alloc] init];
        costLabel.text = [NSString stringWithFormat:@"%d", e.cost];
        costLabel.textColor = [UIColor blueColor];
        [costLabel sizeToFit];
        costLabel.center = CGPointMake((u.center.x + v.center.x) * 0.5, (u.center.y + v.center.y) * 0.5);
        costLabel.layer.cornerRadius = 10;
        costLabel.backgroundColor = [[UIColor whiteColor] colorWithAlphaComponent:0.8];
        costLabel.layer.zPosition = 5;
        [self.view addSubview:costLabel];
    }
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMessage:) name:@"my message" object:nil];
}

- (void)receiveMessage:(NSNotification *)note {
    dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(count * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
        Edge e;
        [note.object getValue:&e];
        
        UIView *u = [self.view viewWithTag:e.u + 1];
        UIView *v = [self.view viewWithTag:e.v + 1];
        UIBezierPath *path = [UIBezierPath bezierPath];
        [path moveToPoint:u.center];
        [path addLineToPoint:v.center];
        CAShapeLayer *line = [CAShapeLayer layer];
        line.path = path.CGPath;
        line.lineWidth = 4;
        line.strokeColor = [UIColor greenColor].CGColor;
        line.fillColor = [UIColor clearColor].CGColor;
        [self.view.layer addSublayer:line];
    });
    count++;
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    shared_ptr<KruskalSolver> cppClass(new KruskalSolver());
    cppClass->solve(edges, 5);
}

@end