489D. Unbearable Controversy of Being - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 489D. Unbearable Controversy of Being

✅ C++ Solution :

 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
 
ll n,m,ans;
vector<int> adj[3002];
 
ll paths[3002][3002];
bool visited[3002];
ll combs[3002];
 
 
ll fact(ll n)
{
  if(n==0 || n==1)
    return 1;
  return n*fact(n-1);
}
 
void func(int v)
{
  int s;
  for(int i=0;i<adj[v].size();i++)
  {
    s=adj[v][i];
    if(!visited[s])
    {
      visited[s]=1;
      func(s);
    }
    for(int j=0;j<adj[s].size();j++)
    {
      if(adj[s][j]!=v)
        paths[v][adj[s][j]]++;
    }
 
  /*  for(int j=0;j<adj[v].size();j++)
    {
      if(adj[v][j]!=s)
        paths[s][adj[v][j]]++;
    }*/
  }
}
 
int main()
{
  int u,v;
  ans=0;
  memset(paths,0,sizeof(paths));
  memset(visited,0,sizeof(visited));
  cin>>n>>m;
 
  combs[0]=0;
  combs[1]=0;
  for(int i=2;i<=n;i++)
    combs[i]=i-1+combs[i-1];
 
 
  for(int i=1;i<=m;i++)
  {
    cin>>u>>v;
    adj[u].push_back(v);
  }
 
  for(int i=1;i<=n;i++)
  {
    if(!visited[i])
    {
      visited[i]=1;
      func(i);
    }
  }
 
 
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(i==j)
        continue;
     //   cout<<paths[i][j]<<" ";
      ans+=combs[paths[i][j]];
    }
  }
  cout<<ans;
 
 
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.