Блог пользователя NeverSee

Автор NeverSee, история, 7 лет назад, По-английски

Have a DAG and we want that for each node v find the number of vertex that existence a path from v to that vertexes
for n <= 1e5

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think simple traversing can helpful.

const int MAX = 100 * 1000 + 11;
int arr[MAX]; //intial all nodes contain 0
vector<int > v[MAX]; // contain edges
void process(int node){
	if(v[node].size() == 0){
		arr[node] = 0;
		return;
	}
	for(int i = 0; i < v[node].size(); i++){
		process(v[node][i]);
		arr[node] += (1 + arr[v[node][i]]);
	}
}
»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

You can use a bit-parallel strategy.

Assuming bit operations for one word is O(1), and let |word| the word-length of your machine, and then the time complexity would be O(NM/|word|). The memory complexity to store the reachability can be O(N*|word|) if you only care about the reachability from |word| vertices at the same time.

In other words, in today's 64-bit environment, it's nearly 64x faster than the naive algorithm to check the reachability from each vertex to all vertices one by one.