Ankur's Blog: Graph Theory

1. 10004 - Bicoloring

2. 336 - A Node Too Far

3. 567 - Risk

4. 10653 - Bombs! NO they are Mines!!

5. 439 - Knight Moves

6. 762 - We Ship Cheap

7. 429 - Word Transformation

LightOj:

1094 - Farthest Nodes in a Tree ( tree Diameter)

1257 - Farthest Nodes in a Tree (II) (tree diameter)

E-Maxx blog problemlist link

Kruskal’s Algorithm [ Minimum Spanning Tree ]

Ankur's BlogJanuary 02, 2019Algorithm, Code Repository, Graph Theory, Kruskal, MST No comments

Kruskal’s Algorithm [ Minimum Spanning Tree ]

গ্রাফ থিওরিতে হাতেখড়ি ৬: মিনিমাম স্প্যানিং ট্রি(ক্রুসকাল অ্যালগোরিদম)

Implementation 01:

#include<bits/stdc++.h>
using namespace std;
const int maxn = (int) 2e5 + 5;

struct edge
{
    int u,v,w;
};

vector<edge>graph, output;
int parent[maxn], mstValue = 0;

bool cmp (edge a, edge b)
{
    return a.w < b.w;
}

int Find(int r)
{
    if(parent[r] == r)
        return r;
    return parent[r] = Find(parent[r]);
}

void initPar(int r)
{
    for(int i = 0; i <= r; i++)parent[i] = i;
}

void kruskals_Algorithm(int n)
{
    sort(graph.begin(), graph.end(), cmp);
    for(int i = 0; i < (int)graph.size(); i++){
        cout << graph[i].u << " "<<graph[i].v << " "<< graph[i].w<<endl;
    }
    initPar(n);
    int cnt = 0;

    for(int i = 0; i < (int)graph.size(); i++){
        int uPr = Find(graph[i].u);
        int vPr = Find(graph[i].v);

        if(uPr != vPr){
            if(cnt == n-1) break;

            output.push_back(graph[i]);
            mstValue += graph[i].w;
            parent[uPr] = vPr;
            cnt++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
   cout.tie(nullptr);
   // freopen("in.txt", "r", stdin);

    int n,e;
    cin >> n >> e;
    cout << n << " & " << e << endl;
    for(int i = 0; i < e; i++){
        int u,v,w;
        cin >> u >> v >> w;
        edge input;
        input.u = u;
        input.v = v;
        input.w = w;
        graph.push_back(input);
    }

    kruskals_Algorithm(n);

    cout << "MST Value : " << mstValue << endl;

    for(int i = 0; i < (int)output.size(); i++){
        cout << output[i].u << " "<<output[i].v << " "<< output[i].w<<endl;
    }

    return 0;
}

Implementation 02:

#include<bits/stdc++.h>
using namespace std;

const int MAX = 300005;
int id[MAX], nodes, edges, idx;

pair <int, pair<int, int> > p[MAX], output[MAX];

void initialize()
{
    for(int i = 0; i < MAX; i++)
    {
        id[i] = i;
    }
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[ id[x] ];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

int kruskal(pair <int, pair<int, int> > p[])
{
    idx = 0;
    int x,y;
    int cost, minimumcost = 0;

    for(int i = 0; i < edges; i++)
    {
        /// selecting edges one by one in increasing order from the beginning.
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        /// check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumcost += cost;
            output[idx++] = make_pair(cost, make_pair(x,y));
            union1(x,y);
        }
    }
    return minimumcost;
}

int main()
{
   // freopen("in.txt", "r", stdin);

        int x,y;
        int weight,cost,minimumcost,price;
        initialize();
        scanf("%d %d", &nodes, &edges);
        //cout << nodes << " & "<<edges<<endl;
        for(int i = 0; i < edges; i++)
        {
            cin >> x >> y >> weight;
            p[i] = make_pair(weight, make_pair(x,y));
        }
        sort(p, p+edges);
       // for(int i = 0; i < edges; i++){
           // cout << p[i].second.first << " "<<p[i].second.second << " "<<p[i].first<<endl;
        //}
        minimumcost = kruskal(p);
        cout << "MST :- ";
        cout << minimumcost<<endl;
        for(int i = 0; i < idx; i++){
            cout << output[i].second.first << " "<<output[i].second.second << " "<< output[i].first << endl;
        }
    return 0;
}

315 - Network

Ankur's BlogDecember 23, 2018Articulation Points and Bridges, Graph Theory, Online Judge, UVA No comments

315 - Network

Topic : Graph Theory(AP)

Solution 01:

#include<bits/stdc++.h>
using namespace std;

#define Max 100000
vector<int> graph[Max];
int parent[Max];
int low[Max];
int d[Max];
int visited[Max];
bool isArticulationPoint[Max];
int Time = 0;

void dfs(int u, int root)
{
    Time = Time + 1;
    visited[u] = Time;
    d[u] = low[u] = Time;
    int noOfChildren = 0;
    for(int i = 0; i <graph[u].size(); i++){
        int v = graph[u][i];
        if(v == parent[u])continue;
        parent[v] = u;
        if(visited[v]) low[u] = min(low[u], d[v]);
        else{
            noOfChildren = noOfChildren + 1;
            dfs(v, root);
            low[u] = min(low[u], low[v]);
            if(low[v] >= d[u] and u != root)isArticulationPoint[u] = true;
        }
    }
    if(u == root and noOfChildren > 1)isArticulationPoint[u] = true;
}

int main()
{
    int n,x,y;
    char c;
    while(cin >> n && n)
    {
        Time = 0;
        for(int t = 0; t <= n; t++){
            graph[t].clear();
            parent[t]= low[t] = d[t] = visited[t] = 0;
            isArticulationPoint[t] = false;
        }
        while(scanf("%d", &x) == 1 && x)
        {
            while(scanf("%d%c", &y, &c) == 2)
            {
                graph[x].push_back(y);
                    graph[y].push_back(x);
                if(c == '\n') break;
            }
        }
        dfs(1, 1);
        cout << count(isArticulationPoint+1, isArticulationPoint+n+1, true)<<endl;
    }
    return 0;
}

Articulation Points and Bridges

Ankur's BlogDecember 23, 2018Algorithm, Articulation Points and Bridges, Code Repository, Graph Theory No comments

Resource:

বাইকানেক্টেড কম্পোনেন্ট , ব্রিজ, আরটিকুলেশন পয়েন্ট [ থিওরি ]

গ্রাফ থিওরিতে হাতেখড়ি ১৩: আর্টিকুলেশন পয়েন্ট এবং ব্রিজ

Finding bridges in a graph in O(N+M)

Finding articulation points in a graph in O(N+M)

Articulation Points:01

#include<bits/stdc++.h>
using namespace std;

#define Max 100000
vector<int> graph[Max];
int parent[Max];
int low[Max];
int d[Max];
int visited[Max];
bool isArticulationPoint[Max];
int Time = 0;

void dfs(int u, int root)
{
    Time = Time + 1;
    visited[u] = Time;
    d[u] = low[u] = Time;
    int noOfChildren = 0;
    for(int i = 0; i <graph[u].size(); i++){
        int v = graph[u][i];
        if(v == parent[u])continue;
        parent[v] = u;
        if(visited[v]) low[u] = min(low[u], d[v]);
        else{
            noOfChildren = noOfChildren + 1;
            dfs(v, root);
            low[u] = min(low[u], low[v]);
            if(low[v] >= d[u] and u != root)isArticulationPoint[u] = true;
        }
    }
    if(u == root and noOfChildren > 1)isArticulationPoint[u] = true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  //  freopen("in.txt", "r", stdin);
    int n,e;
    cin >> n >> e;
    for(int i = 0; i < e; i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1,1);
    for(int i = 1; i <= n; i++){
        if(isArticulationPoint[i])cout << i<<endl;
    }
    return 0;
}

Bridge 01:

#include<bits/stdc++.h>
using namespace std;

#define Max 100000
vector<int> graph[Max];
vector<pair<int, int> > Bridge;
int parent[Max];
int low[Max];
int d[Max];
int visited[Max];
bool isArticulationPoint[Max];
int Time = 0;

void dfs(int u, int root)
{
    int v;
    Time = Time + 1;
    visited[u] = Time;
    d[u] = low[u] = Time;
    int noOfChildren = 0;
    for(int i = 0; i <graph[u].size(); i++){
         v = graph[u][i];
        if(v == parent[u])continue;
        parent[v] = u;
        if(visited[v]) low[u] = min(low[u], d[v]);
        else{
            noOfChildren = noOfChildren + 1;
            dfs(v, root);
            low[u] = min(low[u], low[v]);
            if(low[v] > d[u])
            {
                isArticulationPoint[u] = true;
             //    cout << u << "-------"<<v<<endl;
                 Bridge.push_back({u,v});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("in.txt", "r", stdin);
    int n,e;
    cin >> n >> e;
    for(int i = 0; i < e; i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(1,1);
    for(int i = 0; i < Bridge.size(); i++){
        cout << Bridge[i].first << " "<<Bridge[i].second<<endl;
    }
    return 0;
}

802. Find Eventual Safe States

Ankur's BlogNovember 20, 2018DFS, Graph Theory, LeetCode, Online Judge No comments

802. Find Eventual Safe States

Solution: DFS

concept:

যেই নোডগুলোতে সাইকেল নাই ওই গুলা প্রিন্ট করতে হবে।

Code:

class Solution {
public:

    unordered_set<int> cycle_nodes, safe_nodes;

    bool dfs(vector<vector<int>>& g, int i, unordered_set<int>visited_nodes)
    {
        if(safe_nodes.find(i) != safe_nodes.end())return true;
        if(cycle_nodes.find(i) != cycle_nodes.end())return false;

        if(visited_nodes.find(i) != visited_nodes.end()){
            cycle_nodes.insert(i);
            return false;
        }

        visited_nodes.insert(i);
        for(int node : g[i]){
            if(!dfs(g, node, visited_nodes)){
                cycle_nodes.insert(i);
                return false;
            }
        }
        safe_nodes.insert(i);
        return true;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_set<int>visited_nodes;
        vector<int>ans;

        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph, i,visited_nodes))ans.push_back(i);
        }
        return ans;
    }
};

UVA-10004

Ankur's BlogSeptember 07, 2018Graph Theory No comments

#include<bits/stdc++.h>
using namespace std;
int main()
{
while(1)
{
int n,a;
cin >> n;
if(n == 0)
{
return 0;
}
cin >> a;
int ck = 0;
vector<int> edge[201];
for(int i = 0; i < a; i++)
{
int p,q;
cin>>p>>q;
if(i == 0)ck = p;
edge[q].push_back(p);
edge[p].push_back(q);
}
int color[201];
int is = true;
while(1)
{
for (int i = 0; i < 200; ++i)
{
color[i] = -1;
}
color[ck] = 1;
queue<int>q;
while(!q.empty())q.pop();
q.push(ck);
while(!q.empty())
{
int u = q.front();
// cout<<u<<" //// ";
q.pop();
// if(edge[u][u] == 1)return false;
//cout<<edge[u].size()<<endl;
for(int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i];
//cout<<color[v]<<" "<<color[u]<<" --> "<<u<<" "<<v<<endl;
if(v != u && color[v] == -1)
{
color[v] = 1 - color[u];
q.push(v);
}
else if(color[v] == color[u] && u != v)
{
is = false;
break;
}
}
}
break;
}
if((is))
{
cout<<"BICOLORABLE.\n";
}
else
{
cout<<"NOT BICOLORABLE.\n";
}
}
return 0;
}

Resources:

Resources:

Implementation:

Resources:

Implementation:

Problems:

Problem Link: Round Trip

Resources:

Implementation:

Resources:

Implementation:

Problem link: Coloring Edges on Tree

Explanation: GfG

Implementation:

Resources:

Implementation:

Problems:

Resource:

Topic: DFS

Topic: Topological Sorting

Resource Link

TopSort using DFS:

TopSort using BFS: (Kahn’s algorithm)

Topic: dijkstra

solution 01:

Resource Link

Blog Link:

Implementation:

complexity: O( nodes + edges).

Problem:

Spoj:

Codechef:

uva:

LightOj:

Implementation 01: