2015 ACM Amman Collegiate Programming Contest ( H.Bridge)

Problem link: H. Bridges

Idea: 

 First, find all bridges in the given graph, then remove them from the graph and find all components of the resulting graph.

Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
In the resulting tree, to make an edge not a bridge, it has to be in a cycle, and since all edges in this cycle won't become bridges anymore, you have to create the largest possible cycle, so find the longest path in the tree, and connect it's endpoints. Final answer is : Total number of bridges — length of resulting cycle + 1
Which is equal to : Total number of bridges — longest path in tree.

 

Share:

Read More

ICPC Dhaka Regional Preliminary Contest, 2019

B. The Social Network

Share:

Read More

Number of single cycle components in an undirected graph (CF-977E)

E. Cyclic Components

resource

হিন্টঃ প্রতিটি কম্পোনেন্ট এ চেক করবো তাদের প্রত্যেকটি নোডের ডিগ্রি দুই কিনা, যদি দুই হয় তাইলে সেটা একটা সিঙ্গেল সাইকেল কম্পোনেন্ট।

Share:

Read More