主要思想是并查集,不懂的可以先了解下这个算法再来做题就明白了。
c++实现:
#include<iostream> #include<vector> using namespace std; int f[10000]; //找根节点 int find(int x) { if (f[x] != x) f[x] = find(f[x]); return f[x]; //不要加else!!!!!!!!! } //连接两个集合 void join(int x, int y) { int a = find(x); int b = find(y); if (a < b) //判断两点的根节点大小,合并 f[b] = a; else if (a > b) f[a] = b; } int main() { int n, m; //n:点的个数,m:边 int temp_1, temp_2,count=0; cin >> n >> m; //extern vector<int> f(n+1); for (int i = 1; i <= n; i++) { f[i] = i; } for (int i = 1; i <= m; i++) { cin >> temp_1 >> temp_2; join(temp_1, temp_2); } //与1同属一个根节点即为两点连通 int jiedian_1 = find(1); for (int i = 1; i <= n; i++) { if (jiedian_1 == find(i)) count++; } cout << count << endl; return 0;
以下为java实现代码
import java.util.*; public class Main { static int[] pre; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); pre = new int[n + 1]; for (int i = 1; i <= n; i++) { pre[i] = i; } for (int i = 0; i < m; i++) { int a = sc.nextInt(), b = sc.nextInt(); join(a, b); } int traget = find(1), count = 0; for (int i = 1; i <= n; i++) { int x = find(i); if (traget == x) { count++; } } System.out.println(count); } public static void join(int x, int y) { int fx = find(x), fy = find(y); if (fx > fy) { pre[fx] = fy; } else { pre[fy] = fx; } } public static int find(int x) { if (pre[x] != x) { pre[x] = find(pre[x]); } return pre[x]; } }
标签:pre,连通,temp,int,fy,个数,public,算法,find From: https://www.cnblogs.com/lcllcl/p/17592918.html