我不知道为什么很多题解都有dfs写,直接用并查集不更快一点吗
参考代码:
import java.util.*;
public class Main {
static int[]p=new int[1010];
static int n,m,st,ed;
static int[]x=new int[2010];
static int[]y=new int[2010];
public static void main(String[]args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++) {
p[i]=i;
}
for(int i=1;i<=m;i++) {
x[i]=sc.nextInt();
y[i]=sc.nextInt();
int px=find(x[i]),py=find(y[i]);
if(px!=py)p[px]=py;
}
int ans=0;
st=sc.nextInt();
ed=sc.nextInt();
if(find(st)!=find(ed))System.out.print(-1);
for(int i=1;i<=n;i++) {
if(i!=st&&i!=ed) {
if(check(i)) {
ans++;
}
}
}
System.out.print(ans);
}
public static int find(int x) {
if(p[x]!=x) {
p[x]=find(p[x]);
}
return p[x];
}
public static boolean check(int u) {
for(int i=1;i<=n;i++)p[i]=i;
for(int i=1;i<=m;i++) {
if(x[i]==u||y[i]==u)continue;//删除这个点的边看是否还能连通。
int px=find(x[i]),py=find(y[i]);
if(px!=py)p[px]=py;
}
return find(st)!=find(ed);
}
}
0.0分
0 人评分
震宇大神的杀毒软件 (C++代码)浏览:1118 |
蛇行矩阵 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:575 |
C语言训练-大、小写问题 (C语言代码)浏览:732 |
WU-链表数据求和操作 (C++代码)浏览:1317 |
三角形 (C++代码)递推浏览:760 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:642 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:578 |
1908题解浏览:640 |
简单的a+b (C语言代码)浏览:582 |