答案等于总三角形数-不合法数

一个不合法三角形一定存在两个顶点，在这个三角形中这个顶点的角的两边不同色

 

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6  7 using namespace std; 8 inline int read() 9 {10     int x=0,f=1;char ch=getchar();11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}13     return x*f;14 }15 16 int n,m,ans;17 int deg[1007];18 19 int main()20 {21     n=read(),m=read();22     for (int i=1;i<=m;i++)23     {24         int x=read(),y=read();25         deg[x]++,deg[y]++;26     }27     for (int i=1;i<=n;i++)ans+=(deg[i]*(n-1-deg[i]));28     printf("%d\n",n*(n-1)*(n-2)/6-ans/2);29 }