当前位置:首页 » Project Euler » 详细页

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

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

RecNrCallerCalled
1200007100053
2600183500439
3600863701497
.........

Solution

为每个人分配一个Vector来保存和当前人是朋友的人的编号的集合,于是只需要判断第一个人的朋友是否超过一定数目即可。 新增一通电话时,将他们的朋友集合合并即可。 这里用到了并查集的思想,当两个人的朋友集合合并时,他们两人的朋友集合都会变为同一个,这里的同一个的涵义是朋友的集合这个指针指向同一个Vector实例,则当其中之一改变时,另一个也会一样变化(Vector实例是同一个导致的)。

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