Question

一道算法题,算法好或者搞ACM的童鞋看过来~

Answer 1

你好,我已经ac了,下面是ac代码

思路就是简单并查集

41549wujianan20071012Accepted32148 kb1060 msJava/Edit2012-02-01 00:05:46

import java.math.*;

import java.io.*;

import java.util.*;

import java.lang.*;

public class Main {

public static int father[] = new int[1005];

public static int getFather(int x) {

int ret = x;

while (ret != father[ret]) {

father[ret] = father[father[ret]];

ret = father[ret];

}

return ret;

}

public static void union(int a, int b) {

father[getFather(b)] = father[getFather(a)];

}

public static void main(String[] args) {

Scanner cin = new Scanner(System.in);

int n, m;

while (true) {

n = cin.nextInt();

if (n == 0) {

break;

}

for (int i = 1; i 0) {

int a, b;

a = cin.nextInt();

b = cin.nextInt();

union(a, b);

m--;

}

boolean t[] = new boolean[1005];

int cnt = 0;

for (int i = 1; i