题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6016
题意：给定男羊和女羊的朋友关系，即给定一个图，问从任意一只羊开始连续数四只不相同的羊的方法数。
思路：一开始用了dfs没过，报的超时，以为真的会超时，最后发现，犯了个以前常犯的老问题，存边的vector开小了，，这道题需要开
(n+m)的vector。
后来又按官方题解做了一遍，官方题解，也就需要脑袋转一下。要找序列：男--女--男--女，或者 女--男--女--男；那么只需要找其中一种，即只找 女(1)--男(2)--女(3)--男(4) 的种数，答案为ans*2。枚举(2)号男羊和与(2)号男羊之间有边的一只(3)号女羊，即可确定
一类序列的种数，ans+=(sheep[i]-1)*(sheep[j]-1) i与j之间有边。
dfs：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005 vector<int> sheep[*N]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n+m;i++)
sheep[i].clear();
for(int i=;i<k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
sheep[a].push_back(b+n);
sheep[b+n].push_back(a);
}
long long ans=;
for(int i=;i<=n;i++)
{
int way=sheep[i].size()-;
for(int j=;j<sheep[i].size();j++)
{
ans+=(sheep[sheep[i][j]].size()-)*way;
}
}
printf("%I64d\n",ans*);
}
return ;
}
官方做法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005 vector<int> sheep[*N]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n+m;i++)
sheep[i].clear();
for(int i=;i<k;i++)
{
int a,b;
scanf("%d%d",&a,&b);
sheep[a].push_back(b+n);
sheep[b+n].push_back(a);
}
long long ans=;
for(int i=;i<=n;i++)
{
int way=sheep[i].size()-;
for(int j=;j<sheep[i].size();j++)
{
ans+=(sheep[sheep[i][j]].size()-)*way;
}
}
printf("%I64d\n",ans*);
}
return ;
}