【杭电】[5631]Rikka with Graph

问题描述

Rikka with Graph

[hdu-5631] [3241978769555317] @vjudge

问题分析

给了n点，n+1条边，问存在多少个方案使图去掉几条边后，仍能连通。
由连通图性质知，n个点至少要有n-1条边才能连通
因为数据范围较小
所以尝试采取枚举法看去掉某一条或某两条边后图是否连通
判断图是否连通可用并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
int par[120];
struct node {
    int n,m;
} a[120];
int find(int m) {
    if(m==par[m])
        return m;
    else
        return par[m]=find(par[m]);
}
void unite(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    else
        par[y]=x;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n+1; i++) {
            scanf("%d %d",&a[i].n,&a[i].m);
        }
        int res=0;
        for(int i=0; i<n+1; i++) {
            for(int j=i; j<n+1; j++) {
                for(int k=1; k<=n; k++)
                    par[k]=k;
                for(int k=0; k<n+1; k++) {
                    if(k==i||k==j)
                        continue;
                    unite(a[k].n,a[k].m);
                }
                int k;
                for(k=1; k<n; k++) {
                    if(find(n)!=find(k))
                        break;
                }
                if(k==n)
                    res++;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}