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. Algorithms
  3. Graph Theory
  4. Jogging Cats
  5. Discussions

Jogging Cats

  • comp0zr
     + 1 comment

    In my opinion, the editorial's approach is unnecessarily complex. My approach is as follows:

    WARNING: SPOILERS AHEAD!

    • Store edges in standard adjacency lists for each node, and sort them.
    • Set mid = 1, iterate from 1 to V.
    • Iterate through mid's edges (call these nodes b).
    • Iterate through b's edges (call these nodes a).
    • Count the number of ordered a-b pairs strictly (a < b < mid) (since the adjacency lists are sorted, you can terminate each loop according to this logic).
    • After all edges have been checked, run through the set of counts. For each count, add count * (count - 1) / 2 to the result.
    • Return result.
    #include <bits/stdc++.h>
using namespace std;
typedef long long ULL;

int V, E;
vector<int> adj[50010];

ULL Solve()
{
    ULL res = 0;
        
    for(int mid = 1; mid <= V; mid++)
    {        
        map<int, int> counts;
        
        for(auto b : adj[mid])
        {                              
            if(b >= mid) break;
              
            for(auto a : adj[b])
            {    
                if(a >= mid) break;                      
                
                counts[a]++;                                
            }            
        }
        for(auto it : counts)
        {
            int start = it.first;
            int count = it.second;
                        
            res += (count * (count - 1)) / 2;            
        }
    }    
    return res;
}

int main() 
{
    cin >> V >> E;
    
    for(int i = 0; i < E; i++)
    {
        int a, b;
        cin >> a >> b;
        
        if(a > b) swap(a, b);
                
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i <= V; i++)
    {
        sort(adj[i].begin(), adj[i].end());        
    }    
    cout << Solve() << "\n";
    
    return 0;
}

    return 0;
}