NeverSee's blog

Please Help
By NeverSee, history, 5 years ago, In English

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

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]]);
	}
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is Good but the order is O(n^2);

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not really because you are using the adjacency-list representation of the graph.

      Actually the answer is just to run DFS/BFS on that node and see how many nodes are visited in the process.

      Complexity O(E + V)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That not for each vertex

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Then you can find the condensation graph into SCC and run DFS to find the answer recursively. Complexity doesn't change

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I have modified the code to make it run in O(n)

      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 (arr[node]!=0) return ; //prevents re-calculations
	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]]);
	}
}
      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Can we really compute the number of vertices that can be reached from vertex v with this algorithm?

    I think this graph is a counterexample.

    (UPD: Sorry, the number with the red color font actually should be 6)

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply