### Connectedness of a network题号：186 难度： 60 中英对照

Here are the records from a busy telephone system with one million users:

 RecNr Caller Called 1 200007 100053 2 600183 500439 3 600863 701497 ... ... ...

### Code

import java.util.Arrays;
import java.util.Iterator;
import java.util.Vector;

public final class p186 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static long calls = 0;
static long nums = 0;
static Vector<Integer> cs = new Vector<Integer>(56);
static Vector<Integer>[] hash = new Vector[1000000];

static public String run() {
int PM = 524287;
Vector<Integer> work;
Arrays.fill(hash, null);
while (true) {
// generate a phone call
int from = lagFib();
int to = lagFib();
if (from == to) // misdial
{
continue;
}
calls++;
if (hash[from] == null) {
// first call for from number
if (hash[to] == null) {
// first call for either number
work = new java.util.Vector<Integer>();
work.add(from);
work.add(to);
hash[from] = hash[to] = work;
} else {
work = hash[from] = hash[to];
work.add(from);
}
} else {
if (hash[to] == null) {
work = hash[to] = hash[from];
work.add(to);
} else {
// both numbers have been called
if (hash[from] == hash[to])
continue; // already had one of these calls
// have 2 lists to merge
work = merge(to, from);
}
}

if ((work = hash[PM]) != null) {
// call involved friend(s) of PM
int friends = work.size();
if (friends >= 990000)
return ""+calls;
}

}
}

static int lagFib() {
long S;
nums++;
if (nums < 56)
S = (100003 - 200003 * nums + 300007 * nums * nums * nums) % 1000000;
else {
S = (((Integer) (cs.elementAt(0))).intValue() + ((Integer) (cs
.elementAt(31))).intValue()) % 1000000;
cs.remove(0);
}
cs.add(new Integer((int) S));
return (int) S;
}

static Vector<Integer> merge(int to, int from) {
Vector<Integer> sfrom = hash[from];
Vector<Integer> sto = hash[to];
if (sfrom.size() > sto.size()) {
sfrom = hash[to];
sto = hash[from];
}
Iterator<Integer> it = sfrom.iterator();
while (it.hasNext()) {
Integer num = (Integer) (it.next());
sto.add(num);
hash[num.intValue()] = sto;
}
return sto;
}

}
2325629
2851ms