[learning notes] connectivity and circuit of graph

Graph Subset Problem

The first step is to delete something wonderful .

If the degree of a point < K-1 Then obviously it will not contribute to the answer , It can be deleted by a process similar to topological sorting .

If the degree <= K-1 There are some words left after deleting the dot of , Can solve case 1 .

The size of this question is K The regiment is not easy to find .

My initial practice withered

Consider deleting degrees = K-1 Judge whether this point is in a group .

direct $O(K^2)$ Whether enumeration has two sides .

A little calculation will find the time complexity $O(m\sqrt{m}\log n)$ .

details ： When a point is out of line, delete the point and its adjacent edges , Pay attention to one point. Don't join the team for many times .

Tanya and Password

Take it apart and you will find that this problem is asking you to ask Euler .

You can simulate with stack , After considering a point of immobility , Put this path in reverse order into the answer .

details ： Pay attention to judge the connectivity of the graph , Because it is a directed graph, it is convenient to check the length of the final sequence .

We must judge the degree of nodes first

Data Center Drama

Can't

At first, I was wrong .

In fact, it's easy to think of Euler's circuit when you see the limit that the out and in degrees are even .

The problem is that the Euler loop guarantees the output = The degree of , There is no guarantee that the access is even .

Consider inverting even edges in Euler circuits , In this way, except for the end point, the points on the path must meet the limit .

Finally, determine the total number of edges , If it is an odd number, connect a self ring at the starting point .