1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 using namespace std;10 11 int father[1005];12 13 int getFather (int x) {14     if (x != father[x]) {15         father[x] = getFather(father[x]);16     }17     return father[x];18 }19 20 void Union (int p, int q) {21     int x = getFather (p);22     int y = getFather (q);23     if (x != y) {24         father[y] = x;25     }26 }27 28 void Init (int n) {29     for (int i = 1 ; i <= n; ++ i) {30         father[i] = i;31     }32 }33 34 int main () {35     int T; cin >> T;36     while (T --) {37         int n, op_n;38         cin >> n >> op_n;39         Init(n);40         for (int i = 0 ; i < op_n; ++ i) {41             int x, y; cin >> x >> y;42             Union(x, y);43         }44         int cnt = 0;45         for (int i = 1; i <= n; ++ i) {46             if (father[i] == i) {47                 cnt ++;48             }49         }50         cout << cnt << endl;51     }52     return 0;53 }

 1 import java.util.*; 2 import java.io.*; 3 import java.math.*; 4  5 class DisjointSet{ 6     public static int MAXX = 1005; 7     public int ans = 0; 8     public int father[] = new int[MAXX]; 9     public int vis[] = new int[MAXX];10     11     public DisjointSet(){12         this.ans = 0;13     }14     15     public int GetAns(){16         return ans;17     }18     public int GetFather(int x){19         if(father[x] != 0){20             return GetFather(father[x]);21         }22         else{23             return x;24         }25     }26     27     public void Union(int x, int y){28         int fx = GetFather(x);29         int fy = GetFather(y);30         if(fx != fy){31             father[fy] = fx;32             ans++;33         }34     }35 }36 37 public class Main{38     public static void main(String args[]){39         Scanner in = new Scanner(System.in);40         int l = in.nextInt();41         int a, b, n, opn;42         for(int i = 0; i < l; i++){43             n = in.nextInt();44             DisjointSet D = new DisjointSet();45             opn = in.nextInt();46             for(int j = 0; j < opn; j++){47                 a = in.nextInt();48                 b = in.nextInt();49                 D.Union(a, b);50             }51             System.out.println(n - D.GetAns());52         }53     }54 }