5

Find the ratio between Duplets and Triplets in an undirected Graph

 1 year ago
source link: https://www.geeksforgeeks.org/find-the-ratio-between-duplets-and-triplets-in-an-undirected-graph/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Find the ratio between Duplets and Triplets in an undirected Graph

aeroabrar_31

Given an undirected graph, with n nodes numbered from 0 to n-1. Given a 2D integer array of edges where edges[i]= [ai, bi] denotes that there exists an undirected edge between connected nodes ai and bi. The task is to find the ratio between Duplets and Triplets from the given graph where Duplet can be defined as a component with 2 nodes and a Triplet defined as a component with 3 nodes.

Examples: 

Input: n= 12, edges = [[0, 1], [1, 3], [2, 6], [2, 5], [6, 11], [11, 5], [7, 9], [8, 4], [8, 10]]

duplets_and_triplets-300.jpg

Undirected graph

Output: 1: 2
Explanation: As shown in the above picture, there are 2 triplets and 1 duplet in the graph. So the ratio is 1:2

Approach: The above question can be solved with the following intuition:

A connected component of an undirected graph, as we know, is a subgraph in which each pair of nodes is connected to each other by a path. It means that nodes in a connected component can reach all other nodes in the same connected component. However, if two nodes belong to different components, it is impossible to reach one node from the other. There are total of 4 components in it. We need to find no. of nodes in every component and find their ratio using GCD.

Below are the steps involved in the implementation of the code:

  • Create an adjacency list as a ‘graph‘ containing all neighbors of node index i.
  • Declare a boolean visited array of size n.
  • Declare a temporary ArrayList/vector to store the number of nodes of each component.
  • Iterate through all the nodes from 0 to n-1.
  • Now call the DFS method if the current node is not visited i.e. if vis[i] is false.
  • In the DFS method, count no. of dfs calls made for the neighbor nodes which are unvisited and check whether it is a duplet or triplet as shown in the below code.
  • Now, find the ratio of duplet and triplet using the findRatio() method.
  • Print the answer.

Below is the implementation of the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Depth first traversal
int dfs(vector<vector<int> >& graph, vector<bool>& visited,
        int node)
{
    visited[node] = true;
    int no_of_nodes = 1;
    for (int neighbor : graph[node]) {

        // If a node is not visited
        if (!visited[neighbor]) {
            no_of_nodes += dfs(graph, visited, neighbor);
        }
    }
    return no_of_nodes;
}

// Function to get gcd
int getGCD(int i1, int i2)
{
    if (i1 == i2)
        return i1;
    if (i1 > i2)
        return getGCD(i1 - i2, i2);
    return getGCD(i1, i2 - i1);
}

string getRatio(int duplets, int triplets)
{
    int gcd = getGCD(duplets, triplets);
    int d1 = duplets / gcd;
    int d2 = triplets / gcd;
    string ans = "";
    ans = to_string(d1) + " : " + to_string(d2);
    return ans;
}

// Function to find ratio between duplets
// and Triplets in a graph
string findRatio(int n, vector<vector<int> > edges)
{

    vector<vector<int> > graph;

    for (int i = 0; i < n; i++) {
        graph.push_back({});
    }

    for (int i = 0; i < edges.size(); i++) {
        int x = edges[i][0];
        int y = edges[i][1];
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    int duplets = 0, triplets = 0;

    vector<long long> temp;
    vector<bool> vis(n, false);

    for (int i = 0; i < n; i++) {

        // If not visited
        if (vis[i] == false) {

            // Calling dfs
            int no_of_nodes = dfs(graph, vis, i);
            if (no_of_nodes == 2) {
                duplets++;
            }
            else if (no_of_nodes == 3) {
                triplets++;
            }
        }
    }

    string ans = "";
    if (duplets == 0 && triplets == 0) {
        ans = "0 : 0";
    }
    else if (triplets == 0) {
        ans = to_string(duplets) + " : 0";
    }
    else if (duplets == 0) {
        ans = "0 : " + to_string(triplets);
    }
    else {
        ans = getRatio(duplets, triplets);
    }

    return ans;
}

// Driver code
int main()
{
    vector<vector<int> > edges{
        { 0, 1 }, { 1, 3 }, { 2, 6 }, { 2, 5 }, { 6, 11 }, { 11, 5 }, { 7, 9 }, { 8, 4 }, { 8, 10 }
    };
    int n = 12;

    // Function call
    string ans = findRatio(n, edges);
    cout << "Ratio is = " << ans << endl;

    return 0;
}
Output
Ratio is = 1 : 2

Time Complexity: O(N + E)[DFS] + O(log(min(a, b)) 
Auxiliary Space: O(N+E)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK