Codeforces Round #407 (Div. 2), problem: (D) Weird journey Solution in C

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll in[1000001];
vector<int>adj[1000001];
ll ans=0;
bool g[1000001];
int dfs(int cur)
{
  g[cur]=true;
  int k,cnt=1;
  for(k=0;k<adj[cur].size();k++)
  {
    if(g[adj[cur][k]]==false)
    {
      cnt+=dfs(adj[cur][k]);
    }
  }
  return cnt;
};
ll ct[1000001];
int main()
{
  int n,m,i,u,v;
  cin>>n>>m;
  for(i=0;i<m;i++)
  {
    scanf("%d%d",&u,&v);
    if(u==v)
     ct[u]++;
    else
    {
     adj[u].push_back(v);
     adj[v].push_back(u);
     in[u]++;
     in[v]++;
    }
  }
  int cur=0;
  ll ans=0;
  for(i=1;i<=n;i++)
  {
    if(g[i]==false)
    {
      int tmp=dfs(i);
      if(tmp>1)
       cur++;
      if(tmp==1 && ct[i]>0)
       cur++;
    }
  }
  if(cur>1)
   cout<<"0\n";
  else
  {
    for(i=1;i<=n;i++)
    {
      if(in[i]>1)
      {
        ll tmp=(in[i]*(in[i]-1))/2;
        ans+=tmp;
      }
    }
    ll pt=0,sum=0;
    for(i=1;i<=n;i++)
    {
      pt+=ct[i];
      sum+=in[i];
    }
    sum/=2;
    ans+=(pt*sum);
    ans+=(pt*(pt-1))/2;
    cout<<ans;
  }
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *