23 months ago

Systumm • 200

Mumbai

these are pyq?

10 days ago

Srivarsha • 20

Hyderabad

Solution for Common Companies:
Approach:
 

1. Reading Input:

   • Read all edges as (u, v, company) into edges[].

   • Store unique companies in companies.

2. For Each Company:

   • Build a graph adj[] only for that company.

   • Traverse connected components using DFS.

3. DFS:

   • For each unvisited node, do DFS to explore its connected group.

   • While traversing, track the two largest node IDs in the group.

4. Track Best Answer:

   • For each group, compute a × b where a and b are the two largest nodes.

   • Keep the result with the largest group size, and if equal, the maximum product
     
      

     #include <bits/stdc++.h>
       using namespace std;
     
       int dfs(int node,vector<vector<int>> &adj,vector<bool> &vis,
                 int &largest,int &second_largest){
           
           vis[node] = true;
           int ans = 1;
           
     
           if(node > largest){
             second_largest = largest;
             largest = node;
           }
           else if(node > second_largest){
             second_largest = node;
           }
           
           for(auto child:adj[node]){
             if(vis[child]) continue;
             ans += dfs(child,adj,vis,largest,second_largest);
           }
           
           return ans;
       }
     
       int main() {
     
         int n,m;
         cin >> n >> m;
         
         vector<vector<int>> edges(m,vector<int> (3));
         set<int> companies;
         
         for(int i=0;i<m;i++){
          cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
           companies.insert(edges[i][2]);
         }
     
         long long max_product = 0;
         int max_group_size = 0;
         
         int idx = 0;
         
         for(auto company:companies){
           
           vector<vector<int>> adj(n+1);
           
           while(idx != m){
             if(edges[idx][2] != company) break;
             adj[edges[idx][0]].push_back(edges[idx][1]);
             adj[edges[idx][1]].push_back(edges[idx][0]);
             idx++;
           }
           
           vector<bool> vis(n+1,false);
     
           for(int i=1;i<=n;i++){
             
             if(vis[i]) continue;
             if(adj[i].size()==0) continue;
             
             int largest = 0;
             int second_largest = 0;
             
             int group_size = dfs(i,adj,vis,largest,second_largest);
             
             if(group_size > max_group_size){
               max_group_size = group_size;
               max_product = largest*1LL*second_largest;
             }
             else if(group_size == max_group_size){
               max_product = max(max_product,largest*1LL*second_largest);
             }
           
           }
         }
         
         cout << max_product << endl;
       
         return 0;
     
       }

     Time Complexity: O(n + m) overall, since we process each node and edge at most once across all companies (with ≤100 companies).
     Space Complexity: O(n + m) for adjacency lists, visited array, and edge storage.