LunaticPriest's blog

By LunaticPriest, history, 10 days ago, In English,

Hello, I'm solving a basic connected components . My code is this . I tried switching to bitsets and a map instead of vectors, and also wrote my dfs iteratively in case of stack overflow. What can be the problem? Thanks!

Read more »

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

By LunaticPriest, history, 2 months ago, In English,

Prim's algorithm requires a binary heap. At first, I thought I could easily use a priority queue, but it turns out that I have to reduce the weights of vertices in the priority queue, but it takes O(n) to find the vertex and modify its weight. A min-heap has the ability to reduce the weights of the vertices but it takes a lot of time to code it up, so it isn't useful for competitions. How to reduce the weight of the vertex with less complexity?

Read more »

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

By LunaticPriest, history, 2 months ago, In English,

Is "checking if a graph can be colored by two colors" problem the same as "checking if a graph contains a cycle of an odd number of nodes"? Can we say that a graph is bipartite if it doesn't contain an odd cycle? Are they equivalent statements?

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it