/例如:我有两个列表列表 0: [1,2,3 ](即边: 0-1, 0-2,0-3(
我想检查列表中的顶点是否相互连接,即是否有边 1-2、1-3 等我的方法有效,但由于多个循环,需要花费大量时间。我的代码需要 33 秒才能输入 10^5 个顶点,我想将其减少到 2 秒。
这是我的代码:
public static void ADACHERY() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(br.readLine());
int node = Integer.parseInt(st.nextToken());//total no of vertices
int c = Integer.parseInt(st.nextToken());//total no of edges
ArrayList<Integer>[] adj = new ArrayList[node];
for (int i = 0; i < node; ++i) {
adj[i] = new ArrayList<Integer>();
}
int result=0;
int neg = 0;
while (c != 0) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
//adding edges
adj[a].add(b);
adj[b].add(a);
new line of code
if(!Collections.disjoint(adj[a], adj[b])) neg+=3;
--c;
}
for(int i = 0; i<node; i++) {
int s = adj[i].size();
if(s>1) {
result+= s==2?1: s*(s-1)/2;
int count = 0;
}
}
result-=neg;
out.println(result);
out.close();
}
你的方式是次优的,我闻到这里可以进行一些mapping/ cashing
优化,但我不明白你的格式和任务的确切程度。好的,最后我已经优化了它(3-4 版,哈哈(
它在我蹩脚的电脑上
运行了 0.5 秒
在此处查看不同的图表以查找任何错误:
package cherries;
import java.util.Arrays;
import java.util.Random;
//import strings.ToString;
//import timers.YTimer;
public class AdaAndCherries {
public static void printTable(long[] table, int ySize) {
for (int i = 0; i < table.length; i++) {
//System.out.format("%s ", ToString.toBinaryString(table[i]));
if ((i + 1) % ySize == 0)
System.out.println();
}
}
public static void fillRand(int[] pairs) {
Random r = new Random(System.currentTimeMillis());
int n = pairs.length;
for (int i = 0; i < n;) {
pairs[i++] = r.nextInt(n);
pairs[i++] = r.nextInt(n);
}
}
public static void toTables(long[] tables, int pairs[], int rowSize) {
for (int i = 0; i < pairs.length; i += 2) {
int i2 = i + 1;
int from = pairs[i];
int to = pairs[i2];
// index = starting index of a table + offset, where offset = to/64
int tablesIndex = from * rowSize + (to >> 6);
int shift = to & 63; // offset inside a long digit is to % 64
long bit = 1L << shift;
tables[tablesIndex] |= bit;
// and the same for the table of another node, since graph is bidirectional:
tablesIndex = to * rowSize + (from >> 6);
shift = from & 63;
bit = 1L << shift;
tables[tablesIndex] |= bit;
}
}
public static void main(String[] args) {
int m = 10 * 1000;
int n = m * 2; // in worst case, n = 2*m
// array containing entries like
// [0,1,0,2,2,1,0,3,1,4,5,3
int[] pairs = new int[n];
// each node will have lookuptable of booleans, representing ajancted edge
// this has slightly weird format like
// 0: [0,1,2,3,0...]
// 1: [0,1,2,4,0...]
// 2: [0,1,2,0,0...]
// this tables, each length of 'nodeLookupSize', are concatenated in
a 1d array
// and COMPRIMED AS BOOLEAN FLAGS, each long value has 64 flags
// then looking for cherries is finding differences between two arrays of flags,
// means XORing them:
// [0,1,1,1,0...] (for [0,1,2,3,0...])
// [0,1,1,0,1...] (for [0,1,2,4,0...])
// [0,0,0,1,1,0...] then count ones.
// means 2 cherries found (0,1,3) and (0,1,4) and thats all where node 0
// participates
// after checking pairs 0-1,0-2,0-, the node 0 is done, and must be masked out
// for further pairs like 1-2, etc...
// each row begins from j+1 position, means for 0-3 from position 4,
// because nodes before were already handled,
// because I XOR over length ~n and ~1+2+...n ~ n^2 times, the
algo has O(n^3)
// complexity
// but because not all nodes are connected to each other, i do less XOR's
int rowSize = n / 64 + ((n % 64 == 0) ? 0 : 1);
int allSize = n * rowSize;
System.out.println("size of lookup table of booleans is : " + allSize + " long values what is "
+ (allSize * 8.0) / 1024 / 1024 + " mb, with length of each table in:" + rowSize
+ " long values of size " + rowSize * 8 + " bytes");
long[] tables = new long[allSize];
Arrays.fill(tables, 0);
//YTimer timer = new YTimer();
//timer.start();
// use checks from the page
int[] small = { 0, 1, 0, 2, 2, 1, 0, 3, 1, 4, 5, 3 }; // must be 5 cherries
// small = new int []{ 1, 2, 1, 3, 1, 4, 1,0};// must be 6 cherries
// small = new int []{ 1, 2, 3,2}; // must be 1 cherry
System.arraycopy(small, 0, pairs, 0, small.length);
// fill pairs with random nodes in random order
fillRand(pairs);
// timer.stopAndPrint("pairs initiaded in:");
// fill lookup tables from the pair list:
// timer.start();
toTables(tables, pairs, rowSize);
// timer.stopAndPrint("tables filled in:");
// printTable(tables,rowSize);
// timer.stopAndPrint("rowSize:" + rowSize);
int allCherriesCount = 0;
int n_m_1 = n - 1;
// timer.start();
for (int i = 0, tableStart = 0; i < n_m_1; i++, tableStart += rowSize) {
// System.arraycopy(tables, tableStart, v1Backup, 0, rowSize);
int summ = 0;
int tableStart2Base = tableStart + rowSize;
for (int j = i + 1, tableStart2 = tableStart2Base; j < n_m_1; j++, tableStart2 += rowSize) {
int tablesIndex = tableStart + (j >> 6);
int shift = j & 63;
long bit = 1L << shift;
// true, if i is connected to j:
boolean isConnected = (tables[tablesIndex] & bit) != 0;
if (isConnected) {
// System.arraycopy(tables, tableStart2, v2Backup, 0, rowSize);
// System.out.println( "connected: " + i + " : " + j);
int jNext = j + 1;
int kBegin = jNext >> 6;
int kMaskShift = jNext & 63;
// System.out.println( "kBegin: " + kBegin + ", kMaskShift: " + kMaskShift);
long kMaskBit = ~((1L << kMaskShift) - 1);
// get first long value:
long xor = tables[tableStart + kBegin] ^ tables[tableStart2 + kBegin];
// apply the mask:
xor &= kMaskBit;
summ += Long.bitCount(xor);
// System.out.println( "first xor is:" + ToString.toBinaryString(xor));
kBegin++;
for (int k = kBegin; k < rowSize; k++) {
xor = tables[tableStart + k] ^ tables[tableStart2 + k];
// System.out.println( "next xor is:" + ToString.toBinaryString(xor));
summ += Long.bitCount(xor);
}
}
} // end of iterating over an ajancted list
// cherriesHisto[i] = summ; // also you could fill histo for fun
allCherriesCount += summ;
} // end of main loop.
// timer.stopAndPrint("cherries found:" + allCherriesCount);
System.out.println("cherries found:" + allCherriesCount);
}
}