大家好，我是энтджей，今天是我2026年第十四次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 蛮抽象的，而且题目很绕：
  • 1.按照原图$G$连接$u_i$和$v_i$的一条边，在$L(G)$里创建一个点——$D(u_i,v_i)$
  • 2.遍历$L(G)$里的所有点（两两遍历），设遍历的两个点分别为$D(u_i,v_i)$和$D(u_j,v_j)$，如果$(u_i == u_j || u_i == v_j || v_i == u_j || v_i == v_j)$那么在$L(G)$中$D(u_i,v_i)$和$D(u_j,v_j)$中连接一条线
  • 3.求$L(G)$中一共有多少条线

然后就是写代码

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 其实看到题目并理解后，我的的第一反应都是暴力枚举所有点，寻找$L(G)$中包含相同$G$的点的两个点，然后ans++，但是会爆掉。
  • 自己编了一个样例，画图来解释比较清楚：

  样例：
  5
  1 2
  1 3
  1 4
  1 5
  4 5
  

  画出来的$G$以及$L(G)$长这样：
  
  • 分别求不同颜色的边：
    • 先看红色：
      
      可以看到红色的边是代表共同拥有1的点
    • 再仔细观察：
      • Q：一共有多少个有1的点？ A：4个
      • Q：那跟求线的个数有什么关系呢？A：4-1 + 4-2 + 4-3 + 4-4 = 4-1 + (4-1)-1 + ((4-1)-1)-1 + (((4 -1)-1)-1)-1 看得出来每一个加数都是前一个加数-1，所以我们可以用cnt数组计算$L(G)$中有多少个包含相同$G$中的点的点，然后利用前面的求线的个数的方式算出个数
  • 其他的颜色同红色

• 最后输出（write）：

  • 输出$L(G)$中线的个数

其实有点抽象，还很绕，而且我太挫了，讲不来

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e5 + 10;
int n,m;
int ans;
int cnt[N];
int u[N];
int v[N];
void init() {
    ans = 0;
    memset(cnt, 0, sizeof cnt);
    memset(u, 0, sizeof u);
    memset(v, 0, sizeof v);
}
void read() {
    init();
    cin >> n >> m;
    for(int i = 1; i <= m;  i++){
        cin >> u[i] >> v[i];
        cnt[u[i]]++; //存储L(G)中有多少个包含G中u[i]的点
        cnt[v[i]]++; //存储L(G)中有多少个包含G中v[i]的点
    }
}
void process() {
    for(int i = 1; i <= m; i++) { 
        //处理新增的线
        //根据前面的推导过程，让L(G)中包含G中u[i]的点减去自己这一个点，按理说要再减去前面算过的点，但是上一个点减去了自己这个点，相当于减少了连接这个点的线，cnt[v[i]]--同理
        //用ans记录当前L(G)里有多少条线
        cnt[u[i]]--,cnt[v[i]]--;
        ans += cnt[u[i]] + cnt[v[i]]; 
    }
}
void write() {
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    read();
    process();
    write();
    return 0;
}

---

🎉完结撒花🎉

怎么感觉这篇这么长嘞？