I want to find bridges in an undirected graph without using Tarjan's algorithm(optimal). The edges that are bridges will always be present in all the spanning trees of the graph, can we use this property somehow? I know this is not O(n) but O(nlogn) but still. As of now I found the Spanning trees, and then created another DSU to keep track of nodes using edges other than the spanning tree ones. After this I add the spanning tree edges to see which ones contribute to actual combination of regions. But well, this is wrong as of now, But is there any possibility of this to be solved by Spanning trees?
Consider a ring of nodes. There are no bridges here. You'll need to consider n different spanning trees (each of size n) to ultimately find out that none of the edges in this cycle are relevant to you. That's going to be n^2 on its face.
So to do something fast you'll need to go through all spanning trees at once, and then look at how they interact. One way to think about it is: use one spanning tree, and then delete paths on it for each additional edge in the graph. But that's just a rephrased way to describe Tarjan's algorithm fundamentally. You're just hiding the DFS tree somewhere else.
You can also use a dynamic connectivity approach and sweep through spanning trees. You can duplicate all edges, and add a billion to the weights of the second copy of each edges. Then maintain a Min spanning tree with dynacon while always deleting the smallest-weight edge in the graph. The bridges will be the edges that get replaced by their bigger copy of themself when they get deleted. This is a million times harder and probably a log factor slower and at least 300 lines more code, but I'm convinced it could be made to work with enough motivation.
Thanks for the comment! You said this: "use one spanning tree, and then delete paths on it for each additional edge in the graph", How do I delete paths on it? I am using a DSU only right to store the nodes, how do I delete edges and find out new connectivity, wouldn't that be around n^2? Sorry, I could not understand the dynamic connectivity part though, will have to read that part first. Thanks for the help!