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

|

187 Discussions

|

  • 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.

  • choonhong1998
     + 0 comments

    Python

    def componentsInGraph(gb):
    clusters = []
    for a, b in gb:
        clusters_to_fuse = []
        for cluster in clusters:
            if a in cluster or b in cluster:
                clusters_to_fuse.append(cluster)
        if clusters_to_fuse:
            fused_cluster = {a, b}
            for cluster in clusters_to_fuse:
                for node in cluster:
                    fused_cluster.add(node)
                clusters.remove(cluster)
            clusters.append(fused_cluster)
        else:
            clusters.append({a, b})
    clusters_len = list(map(len, clusters))
    return [min(clusters_len), max(clusters_len)]

  • tuph4031
     + 0 comments

    2 ways to solve this problem: - Use DFS: - Use Union Find data structure

    See my solution here: https://github.com/tuphan22028238/DSA/tree/main/ComponentInGraph