fork download
copy 
  1. import sys
  2. sys.setrecursionlimit(2*(10**5))
  3. import threading
  4. threading.stack_size(2**26)
  5. from sys import stdin, stdout
  6. def ain():
  7.     return map(int,sin().split())
  8. def sin():
  9.     return stdin.readline().strip()
  10. """**************************************************************************"""
  11. def main():
  12.     def dfs(v,pv):
  13.         p[v]=1
  14.         id[0]+=1
  15.         low[v]=id[0]
  16.         ids[v]=id[0]
  17.         for to in ad[v]:
  18.             if(to==pv):
  19.                 continue
  20.             if(p[to]!=1):
  21.                 dfs(to,v)
  22.                 low[v]=min(low[v],low[to])
  23.                 if(ids[v]<low[to]):
  24.                     a=v
  25.                     b=to
  26.                     if(a>b):
  27.                         a,b=b,a
  28.                     bri.add((a,b))
  29.             else:
  30.                 low[v]=min(low[v],low[to])
  31.     n,m=ain()
  32.     ad=[[] for i in range(n+1)]
  33.     q1=set()
  34.     for i in range(m):
  35.         x,y=ain()
  36.         if(x>y):
  37.             x,y=y,x
  38.         q1.add((x,y))
  39.         ad[x].append(y)
  40.         ad[y].append(x)
  41.     p=[0]*(n+1)
  42.     id=[0]
  43.     low=[0]*(n+1)
  44.     ids=[0]*(n+1)
  45.     bri=set()
  46.     dfs(1,0)
  47.     q={}
  48.     indc=[{} for i in range(n+1)]
  49.     for i in range(1,n+1):
  50.         for j in ad[i]:
  51.             if(indc[i].has_key(len(ad[j]))):
  52.                 indc[i][len(ad[j])]+=1
  53.             else:
  54.                 indc[i][len(ad[j])]=1
  55.     for i in q1:
  56.         a=len(ad[i[0]])
  57.         b=len(ad[i[1]])
  58.         if(a>b):
  59.             a,b=b,a
  60.         if(q.has_key((a,b))):
  61.             q[(a,b)]+=1
  62.         else:
  63.             q[(a,b)]=1
  64.     f=[0]*n
  65.     for i in range(1,n+1):
  66.         f[len(ad[i])]+=1
  67.     s=0
  68.     for i in q1:
  69.         if(i in bri):
  70.             continue
  71.         a=i[0]
  72.         b=i[1]
  73.         a1=len(ad[a])
  74.         b1=len(ad[b])
  75.         k=0
  76.         if(indc[a].has_key(b1-1)):
  77.             k+=indc[a][b1-1]
  78.         if(indc[b].has_key(a1-1)):
  79.             k+=indc[b][a1-1]
  80.         if((a1+1)==b1):
  81.             if(indc[a].has_key(a1-1)):
  82.                 k-=indc[a][a1-1]
  83.         if((b1+1)==a1):
  84.             if(indc[b].has_key(b1-1)):
  85.                 k-=indc[b][b1-1]
  86.         if(a1>b1):
  87.             a1,b1=b1,a1
  88.         f[a1]-=1
  89.         f[b1]-=1
  90.         f[a1-1]+=1
  91.         f[b1-1]+=1
  92.         if(a1!=b1):
  93.             p=f[a1-1]*f[b1-1]
  94.             p-=1
  95.         else:
  96.             p=(f[a1-1]*(f[a1-1]-1))/2
  97.             p-=1
  98.         if(q.has_key((a1-1,b1-1))):
  99.             p-=q[(a1-1,b1-1)]
  100.         p-=k
  101.         s+=p
  102.         f[a1]+=1
  103.         f[b1]+=1
  104.         f[a1-1]-=1
  105.         f[b1-1]-=1
  106.     print s
  107. threading.Thread(target=main).start()
Success #stdin #stdout 0s 154752KB
comments (?)
stdin
copy 
4 4
1 2
1 3
2 3
1 4
stdout
copy 
4
https://ideone.com/sVl1P7
language:
Python (cpython 2.7.16)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!