Self doubt

Question

The time complexity required to find the number of cut vertex in a undirected simple graph is?If adjacency list representation is given? Is O(V+E) OR O(E)

Comments

Consider this graph the degrees are:

1->1
2->2
3->1
4->3
5->3

Now suppose if we scan through the vertices and we see the adjacency list of  4 we see 1,2 ,5 now the edge 41,42,45 contributes 1 to the degree of 1,2,5 and 3 to degree of 4.If we remove 4 then  we have to remove the edges 41,42,45 right.

So  now we decrease the degree of 1,2,5 by 1 after removing 4 and the edges  41,42,45.

degree:
1->0(See it is so this way we could check other vertices also )
2->1
5->2
3->1

So we see that removing 4 we get 2 components - (1) and(2,3,5) thus 4r is a cut vertex and the time to find weather 4 is a cut vertex or not is basically the no of  edges it is associated with.

Note : while implementing the code we would not store the decremented data otherwise we  will not be able to get the valid answer for other vertices.And one more thing it is degree not indegree in my previous comment.

---

@Doraemon what about this case :-

---

@ankitgupta.1729 This case never came to my mind let me think about this.:)