给出一些成对的公羊与母羊,他们之间是朋友关系(给出的关系是双向的),请列出有多少种四只羊之间的关系(这个关系是单向的,也就是说顺时针转一圈和逆时针转一圈来数都算不同的关系)。

一开始直接dfs暴力,然后无限RE(vector数组开小)和TLE,后来直接计算,以当前点的边减去1再乘以相邻点的边数减去1的值之后再乘以2就是他们的所有关系数就AC了。


代码:

StatusAccepted
Time670ms
Memory8228kB
Length829
LangC++
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 200005
const int len=100000;
vector<int> res[MAX];
int t, n, m, k, x, y;
long long ans;
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d%d%d", &n, &m, &k);
        ans = 0;
        int tmax=n>m?n:m;
        for(int i=1;i<=tmax;i++){
            res[i].clear();
            res[i+len].clear();
        }
        while(k--){
            scanf("%d%d", &x, &y);
            res[x].push_back(y+len);
            res[y+len].push_back(x);
        }
        for(int i=1;i<=n;i++){
            int now=res[i].size();
            for(int j=0;j<now;j++){
                int border = res[res[i][j]].size();
                ans+=(now-1)*(border-1);
            }
        }
        printf("%lld\n", ans*2);
    }
    return 0;
}