思路

首先添加一条边变成基环树，基环树中恰好有 n 条边，因此初始的 m = n - 1 才可能有合法方案。

之后考虑只能添加一条边，最多只能有两个连通块

• 一个连通块，这个连通块就是一棵树，那么不能连出一条自环，答案就是：$\frac{n\times (n-1)}{2} - (n - 1)$

• 两个连通块，此时两个连通块必然是一棵树和一棵基环树，大小为 $n_1$ 和 $n_2$。那么答案为 $n_1\times n_2$

时间复杂度：$O(n\log n)$

代码

java

import java.util.*;

public class Main {
    static int[] pre;
    static int find(int x) {
        if (pre[x] == x) {
            return x;
        }
        pre[x] = find(pre[x]);
        return pre[x];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        if (m != n - 1) {
            System.out.println(0);
            return;
        }
        pre = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = i;
        }
        for (int i = 1; i < n; ++i) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            int fu = find(u);
            int fv = find(v);
            if (fu != fv) {
                pre[fu] = fv;
            }
        }
        int cnt = 0;
        int[] siz = new int[n];
        for (int i = 0; i < n; ++i) {
            if (find(i) == i) {
                cnt += 1;
            }
            siz[find(i)] += 1;
        }
        if (cnt > 2) {
            System.out.println(0);
        } else {
            if (cnt == 1) System.out.println(n * (n - 1L) / 2 - (n - 1));
            else {
                long a = -1, b = -1;
                for (int v : siz) {
                    if (v > 0) {
                        if (a == -1)
                            a = v;
                        else
                            b = v;
                    }
                }
                System.out.println(a * b);
            }
        }
    }
}

C++

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int fa[N];

int mfind(int x){
    if(fa[x]!=x){
        fa[x]=mfind(fa[x]);
    }
    return fa[x];
}

void join(int x,int y){
    int fx=mfind(x);
    int fy=mfind(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}


int main(){
    int n,m;
    cin>>n>>m;

    if(m<n-1){
        cout<<0<<endl;
        return 0;
    }

    for(int i=1;i<=n;i++){
        fa[i]=i;
    }

    bool flg=true;

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        if(mfind(u)==mfind(v)) flg=false;
        join(u,v);
    }

    int numtree=0;
    unordered_map<int,int> h;
    for(int i=1;i<=n;i++){
        h[mfind(i)]++;
        if(mfind(i)==i){
            numtree++;
        }
    }

    if(numtree>2){
        cout<<0<<endl;
    }else{
        if(numtree==1){
            if(flg){
                cout<<1ll*n*(n-1)/2-(n-1)<<endl;
            }else{
                cout<<0<<endl;
            }
        
        }else{
            int res=1;
            for(auto [k,v]:h){
                res*=v;
            }
            cout<<res<<endl;
        }
    }

    // if(numtree>2){
    //     cout<<0<<endl;
    // }else if(!flg){
    //     if(numtree==1){
    //         cout<<0<<endl;
    //     }else{
    //         int res=1;
    //         for(auto [k,v]:h){
    //             res*=v;
    //         }
    //         cout<<res<<endl;
    //     }
    // }else{
    //     cout<<n*(n-1)/2-(n-1)<<endl;
    // }

    return 0;
}

python

class DisjointSet:
    def __init__(self, n):
        self.pa = [i for i in range(n)]  # Correct instance variable initialization

    def find(self, u):
        # Find the representative of the set containing u with path compression
        if self.pa[u] != u:
            self.pa[u] = self.find(self.pa[u])
        return self.pa[u]  # Correct return variable

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu != pv:
            self.pa[pu] = pv

# Input handling
n, m = map(int, input().split())
disjointset = DisjointSet(n)
for i in range(m):
    u, v = map(int, input().split())
    disjointset.union(u-1, v-1)

# Calculate the number of connected components
cop = 0
for i in range(n):
    if disjointset.find(i) == i:
        cop += 1

if cop == 1:
    if m >=n:
        print(0)
    else:
        print((n - 1) * n // 2 - (n-1))
elif cop == 2:
    dic = {}
    for i in range(n):
        root = disjointset.find(i)
        if root not in dic:
            dic[root] = 0
        dic[root] += 1
    ans = 1
    for k in dic:
        v = dic[k]
        ans *= v
    print(ans)

else:
    print(0)

题目描述

定义基环树为$n$个点、条边且不包含重边和自环的无向连通图。形象化的描述，基环树可以由一棵树再添加一条边后形成(不能是树上已存在的边)现在薯条哥拿到了一个无向图，她想连一条边使得这个无向图变成基环树。

薯条哥想知道，有多少种不同的连边方案?

输入描述

第一行输入两个正整数$n,m(1\le n,m\le 10^5)$，代表> 无向图的点数和边数。 接下来的$m$行，每行输入两个正整数$u,v(1\le u,v\le n)$，代表节点$u$和节点$v$有一条边连接。保证给定的无向图不包含重边和自环。

输出描述

输出一个整数，代表添加边的方案数。

样例1

输入

4 4
1 2
1 3
2 3
2 4

输出

0

样例解释

本身该无向图已经是基环树，因此方家数为$0$。

样例2

输入

4 3
1 2
1 3
2 3

输出

3

样例解释

第一个方案:连接$1$和$4$。

第二个方案:连接$2$和$4$。

第三个方案:连接$3$和$4$。