九度-1526-朋友圈[解题代码] | Acm之家
- 假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友…),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
- 输入:
- 输入包含多个测试用例,每个测试用例的第一行包含两个正整数 n、m,1=<n,m<=100000。接下来有m行,每行分别输入两个人的编号f,t(1=<f,t<=n),表示f和t是好友。 当n为0时,输入结束,该用例不被处理。
- 输出:
- 对应每个测试用例,输出在这n个人里一共有多少个朋友圈。
- public static void main(String[] args) throws Exception{
- StreamTokenizer st = new StreamTokenizer(System.in);
- while (st.nextToken() != StreamTokenizer.TT_EOF) {
- int n = (int) st.nval;
- if (n == 0) {
- break;
- }
- if (n == 1) {
- System.out.println(1);
- }else {
- int []parent = new int[n+1];
- for (int i = 1; i <= n; i++) {
- parent[i] = i;
- }
- st.nextToken() ;
- int m = (int) st.nval;
- for (int i = 0; i < m; i++) {
- st.nextToken() ;
- int f = (int) st.nval;
- st.nextToken() ;
- int t = (int) st.nval;
- union(f ,t , parent );
- }
- for (int i = 1; i < n+1; i++) {
- parent[i] = findParent(i, parent);
- }
- Set<Integer> numSet = new HashSet<Integer>();
- for (int i = 1; i < n+1; i++) {
- numSet.add(parent[i]);
- }
- System.out.println( numSet.size());
- }
- }
- }
- private static void union(int f, int t, int[] parent ) {
- int a = findParent(f , parent);
- int b = findParent(t , parent);
- if (a == b) return;
- if (a > b) {
- parent[a] = b;
- } else {
- parent[b] = a;
- }
- }
- private static int findParent(int f, int[] parent) {
- if (parent[f] == f) {
- return f;
- }
- return findParent(parent[f],parent );
- }
- private static int findParent(int f) {
- while (parent[f] != f) {
- f = parent[f];
- }
- return f;
- }
int find(int x) { if(father[x] != x) { father[x] = find(father[x]); } return father[x]; } void merge(int a, int b) { int fa = find(a); int fb = find(b); if(fa == fb) return; father[fa] = fb; } int main() { int n, m; while(scanf("%d", &n) && n != 0) { scanf("%d", &m); for(int i = 1; i <= n; i ++) father[i] = i; int a, b; for(int i = 0; i < m; i ++) { scanf("%d%d", &a, &b); merge(a,b); } int cnt = 0; for(int i = 1; i <= n; i ++) { if(father[i] == i) cnt++; } cout << cnt << endl; } return 0; }Read full article from 九度-1526-朋友圈[解题代码] | Acm之家