Graph_algorithms.sublime-snippet

<snippet>
	<content><![CDATA[
//------------kruskal's---------------

struct DSU {
    vector<int> par, rnk, sz;
    int c;

    DSU(int n) : par(n + 1), rnk(n + 1, 0), sz(n + 1, 1), c(n) {
        for (int i = 1; i <= n; ++i) par[i] = i;
    }

    int find(int i) {
        return (par[i] == i ? i : (par[i] = find(par[i])));
    }

    bool same(int i, int j) {
        return find(i) == find(j);
    }

    int get_size(int i) {
        return sz[find(i)];
    }

    int count() {
        return c;   
    }

    int Union(int i, int j) {
        if ((i = find(i)) == (j = find(j))) return -1;
        else --c;
        if (rnk[i] > rnk[j]) swap(i, j);
        par[i] = j;
        sz[j] += sz[i];
        if (rnk[i] == rnk[j]) rnk[j]++;
        return j;
    }
};

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return a.second.second < b.second.second;
}

int spanningTreeKruskals(vector<vector<int>> adj[], int v) {
    DSU dsu(v);
    vector<pair<int, pair<int, int> > > vp;
    for (int i = 0; i < v; ++i) {
        for (auto edge: adj[i]) {
            pair<int, int> p = {edge[0], edge[1]};
            vp.push_back({i, p});
        }
    }

    sort(vp.begin(), vp.end(), comp);
    int cost = 0;
    for(auto edge: vp){
        if(dsu.Union(edge.first, edge.second.first) != -1){
            cost += edge.second.second;
        }
    }
    return cost;
}

//-----------prims---------------

int spanningTreePrims(vector<vector<int>> adj[], int v) {
    //typedef pair<int, int> pii;
    vector<bool> vis(v);
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push({0, 0});
    int ans = 0;
    while(q.size()){
        auto tp = q.top();
        q.pop();
        
        int vert = tp.second, dis = tp.first;
        if(vis[vert]) continue;
        ans += dis;
        vis[vert] = 1;
        for(auto nbr: adj[vert]){
            if(vis[nbr[0]]) continue;
            q.push({nbr[1], nbr[0]});
        }
    }
    return ans;
}

vector<int> dijkstra(vector<vector<int>> adj[], int v, int src) {
    vector<int> ans(v, INT_MAX);
    ans[src] = 0;
    set<pair<int, int> > s;
    s.insert({0, src});
    while(s.size()) {
        auto p = *s.begin();
        s.erase(s.begin());

        int dis = p.first;
        int node = p.second;

        for (auto p: adj[node]) {
            int nbr = p[0], cost = p[1];
            if(dis + cost < ans[nbr]) {
                if(ans[nbr] != INT_MAX) s.erase({ans[nbr], nbr});
                ans[nbr] = dis + cost;
                s.insert({ans[nbr], nbr});
            }
        }
    }
    return ans;
}

// Bridges
void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v])
                IS_BRIDGE(v, to);
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}


//Articulation points
void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] >= tin[v] && p!=-1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if(p == -1 && children > 1)
        IS_CUTPOINT(v);
}

void find_cutpoints() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>Graphalgos</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>