当前位置：首页 > news >正文

D - New Friends(AtCoder Beginner Contest 350)

news 2025/7/23 17:16:27

题目链接:

D - New Friends (atcoder.jp)

题目大意:

题目解析:

题目的大致意思: 假如A和B是朋友 B和C也是朋友那么当A和C不是朋友的时候可以通过B让A和C也成为朋友问你增加了多少对的朋友关系

题目分析:

咱们可以从图论去考虑当这一群是一个连通块那么这一群点(人) 都是可以通过这个连通块去成为朋友的那么假如这个连通块有N个人那么就会有 N * (N - 1) / 2 条边(朋友关系) 那么全部的连通块减去之前的M条原有的朋友关系就是答案注意开long 存取答案

那么问题来了怎么去看他们是不是在一个连通块 并查集出手了

复习一下并查集让点y到点x的连通下那么就是p[find(y)] = find(x) 直接就过去了

代码:

import java.util.*;// 我认为这个题是并查集的题
public class D {public static int[] p = null; // 表示的是父亲public static void main(String[] args) {var sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();p = new int[n + 10];for(int i = 1; i <= n; i ++ ) {p[i] = i; // 刚开始的祖宗 都是自己自己}long ret = 0;int mm = m;var mp = new HashMap<Integer, Long>();var se = new TreeSet<Integer>();while(m -- != 0 ) {int x = sc.nextInt();int y = sc.nextInt();// 这里理解为y加到x的节点下面p[find(y)] = find(x); // 该不会是这里出问题了吧}for(int i = 1; i <= n; i ++ ) {int x = p[find(i)];if(!mp.containsKey(x)) {mp.put(x, 0l);}long t = mp.get(x) + 1;mp.put(x, t);se.add(x); // 这里面存的是 都是祖宗}for(int i : se) {//System.out.print("i = " + i + "\n");//System.out.print("x = " + mp.get(i) + "\n");long tt = mp.get(i);long t2 = mp.get(i) - 1;ret += tt * t2 / 2;//System.out.print("ret = " + ret + "\n");}ret -= mm;System.out.print(ret);}public static int find(int x) {if(x != p[x])p[x] = find(p[x]);return p[x];}
}