HThinh's blog

GIVE ME SOME IDEA TO SOLVE THIS GRAPH PROBLEM PLS
By HThinh, history, 2 months ago, In English

given a directed graph with n nodes and m edges. find all edges that are present in every cycle of the graph

constraints: n<=1000 m<=20000 TL: 0.9s

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

»
2 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Given the low n, we should be considering O(nm) solutions

Find any cycle (if there isn't any then the answer is an empty set). The number of edges in this cycle is not greater than n. Then, for each edge in the cycle, remove it and try to find another cycle. If you don't find one, then that edge was present in every cycle.

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I feel a tingle of anticipation for an incredible rant soon coming from user Toinfinity

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sometimes, when you are unable to solve a problem, you must look into yourself. Self evaluation is an important skill which you must use if you wish to become good at competitive programming. By analyzing yourself, you can find faults within yourself that are holding you back. For many people who fail to break through to high ranks of Codeforces, these faults terrorize their life and hold them back in many other places other than Codeforces. By removing these faults from your inner being, you can improve your life and Codeforces skills drastically. It is important to remove the lust for women (or men if you are gay), or even conversing with women or the gender to which you are sexually attracted, and instead replace it with 6 hours of edging a day. 6 hours of edging a day has scientifically been proven to improve your cognitive abilities and physical health. By edging 6 hours a day, impurities are removed from your body, cleaning up your bloodstream. When I started edging, I noticed a few changes. Within a week, I started feeling a lot more energy, my need for sleep having been nullified. Within a month, my IQ went up, I was originally tested at 78 IQ, but after 1 month of edging and abstaining from conversing with women, it was 153. It has since been a year since I have started edging, now I have grown from 170cm to 188cm, I have obtained the musculature of a Greek God despite never working out, and can run 5 kilometers in 16 minutes despite never running. I hope my story motivates you, as edging every day has turned me into a superhero, and significantly improved my CP skills. I believe that if you stop what you are doing right now, and edge for 6 hours straight, you will be able to solve this problem.

Best of luck and happy edging,

Toinfinity

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

    Hello Mr. Toinfinity, aka Pubert Brocketti. I remember you giving me this advice when I was a young boy, and even since I was 8 years of age, I have followed this advice earnestly. It has been of my greatest priority in life to never miss a single day of edging. Since I was 8 years old, I have not talked to a single woman, including my mom and grandma. Your advice has greatly improved my life. I was born African but after edging enough, I was lucky enough to get upgraded to Chinese, and someday I believe that if I edge enough, I will become White. I hope that anyone who reads this message realizes the true importance of edging and takes Pubert's advice to heart.

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

      Thank you for your wonderful response. have here a very helpful graph of codeforces rating vs hours of edging, fact checked by me. very concrete proof of the benefits edging can give to your performance. rating-vs-edging

      → Reply