Give an O(n+m) algorithm that returns a node for which if we delete we get a maximum number of components

algorithmsgraph theory

I have this homework :

Give an O(n+m) algorithm that returns a node of an undirected graph for which if we remove it, the remaining graph will consistent of the maximum number of components.

My idea:
First, i thought if we delete the node with max degree we get the result. But since it says O(n+m) i thought maybe i should use DFS. I read that DFS can help to look for bridges, but it doesn't give back a node but an edge instead. So my question, can i use DFS and look for bridges and for all vertices with bridge i use the one with max degree and that's the answer.

Is it correct? Or looking for vertices with bridges is a bad idea? I would appreciate any help.

Best Answer

On GeeksForGeeks has a simple explanation for your question, for computing the articulation points. GeeksForGeeks.