We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Disjoint Set
  4. Components in a graph
  5. Discussions

Components in a graph

Sort by

recency

|

189 Discussions

|

  • fard_nathan
     + 0 comments

    Typescript solution. it passes all tests. (DFS)

    function bfs(graph: number[][], start: number):number[] {
    const queue: number[] = [start];
    const visited = new Set<number>();

    while (queue.length > 0) {
        const selectedNode = queue.pop();
        if (!visited.has(selectedNode)) {
            visited.add(selectedNode);

            for (let node of graph) {
                if (node[0] == selectedNode) {
                    queue.push(node[1]);
                }
                if (node[1] == selectedNode) {
                    queue.push(node[0]);
                }
            }
        }
    }

    return Array.from(visited)

}

function componentsInGraph(gb: number[][]): number[] {
    // Write your code here
    const nodes = new Set<number>();
    for (let g of gb) {
        nodes.add(g[0]);
        nodes.add(g[1]);
    }

     let max = 0;
    let min = nodes.size  ;
    nodes.forEach((index) => {
        // if(index > nodes.size / 2){return}
        const bfsssss = bfs(gb, index);
        bfsssss.forEach(b => nodes.delete(b));
        const value = bfsssss.length;
        if (value > max) {
            max = value;
        }
        if (value < min && value > 1) {
            min = value;
        }
    })
    // console.log([min,max]);

    return [min, max];
}

  • merajhussain1
     + 1 comment

    Is it safe to assume number of nodes as bg.size()*n . I need some help in understanding this?

  • btech2021_priya1
     + 0 comments

    vector componentsInGraph(vector> gb) {

    int n=gb.size()*2;
vector<vector<int>>adj(n+1);
for(int i=0;i<gb.size();i++){
    int u=gb[i][0];
    int v=gb[i][1];
    adj[u].push_back(v);
    adj[v].push_back(u);

}
vector<bool>visited(n+1,0);

int mini=INT_MAX;
int maxi=INT_MIN;

for(int i=1;i<=n;i++){
    if(!visited[i]){
        int cnt=0;
         queue<int>q;
        visited[i]=1;
        q.push(i);
        while(!q.empty()){
            int node=q.front();
            q.pop();
            cnt++;
            for(auto j=0;j<adj[node].size();j++){
                if(!visited[adj[node][j]]){
                    visited[adj[node][j]]=1;

                    q.push(adj[node][j]);
                }
            }
        }
        if(cnt!=1){
        mini=min(mini,cnt);
        maxi=max(maxi,cnt);
        }




    }
}
vector<int>ans;
ans.push_back(mini);
ans.push_back(maxi);

return ans;

    }

  • nvminh
     + 0 comments

    Java solution

    public static List<Integer> componentsInGraph(List<List<Integer>> gb) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(List<Integer> line : gb) {
            int p1 = line.get(0);
            int p2 = line.get(1);
            Set<Integer> s1 = map.get(p1);
            Set<Integer> s2 = map.get(p2);
            if(s1 == null || s2 == null) {
                Set<Integer> s = (s1 == null) ? s2 : s1;
                if(s == null) {
                    s = new HashSet<>();
                }
                s.add(p1);
                s.add(p2);
                map.put(p1, s);
                map.put(p2, s);
            } else {
                if(s1 != s2) {
                    s1.addAll(s2);
                    for(int i: s2) {
                        map.put(i, s1);
                    }
                    map.put(p2, s1);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(Set<Integer> s: map.values()) {
            min = Math.min(min, s.size());
            max = Math.max(max, s.size());
        }
        return Arrays.asList(min, max);
    }

  • wopiyeb362
     + 0 comments

    In graph theory, components refer to distinct subgraphs within a graph where any two vertices are connected by paths. spectrum billing support A component is maximal, meaning no additional edges or vertices from the original graph can be added without losing its connectivity. Identifying components is crucial for analyzing the structure and properties of graphs, aiding in network analysis, clustering, and connectivity studies.