1.P8605 [蓝桥杯 2013 国 AC] 网络寻路

题目链接：P8605 [蓝桥杯 2013 国 AC] 网络寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析：我们的做法是记录所有点的度，然后枚举一个点所有相连接的点，他们之间的合法路径的总条数为：
(d[i]-1)*（d[j]-1)，减1是因为减掉了两个点之间相连的边。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e4+10;
 4 const int M=2e5+10;
 5 int e[M],ne[M],h[N],idx;
 6 int n,m,d[N],ans;
 7 void add(int a,int b)
 8 {
 9     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
10 }
11 int dfs(int u)
12 {
13     int res=0;
14     for(int i=h[u];i!=-1;i=ne[i])
15     {
16         int j=e[i];
17         if(j>u)//防止重复来回搜索，必须要确定一个大小关系
18         {
19             res+=(d[u]-1)*(d[j]-1);
20         }
21     }
22     return res;
23 }
24 signed main()
25 {
26     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
27     memset(h,-1,sizeof h);
28     cin>>n>>m;
29     int a,b;
30     for(int i=0;i<m;i++)
31     {
32         cin>>a>>b;
33         d[a]++,d[b]++;
34         add(a,b),add(b,a);
35     }
36     for(int i=1;i<=n;i++)
37     {
38         ans+=dfs(i);
39     }
40     ans=ans*2;
41     cout<<ans<<endl;
42     return 0;
43 }