By samadeep, history, 10 months ago,

CSES Problem : Advanced Techniques Section

Is there a explanation and proof anyone can suggest me.

You are given an undirected graph that has n nodes and m edges.

We consider subgraphs that have all nodes of the original graph and some of its edges. A subgraph is called Eulerian if each node has even degree.

Your task is to count the number of Eulerian subgraphs modulo 109+7 .

Input

The first input line has two integers n and m : the number of nodes and edges. The nodes are numbered 1,2,…,n .

After this, there are m lines that describe the edges. Each line has two integers a and b : there is an edge between nodes a and b . There is at most one edge between two nodes, and each edge connects two distinct nodes.

• 0

 » 7 weeks ago, # |   +1 Hi samadeep ! The answer is given by the formula 2**k , where k = number of back-edges in the graph. For this to make sense, think that you will hold a set S in which each element is a subset of edges that together generate a simple cycle. Each of those elements are composed by one back-edge and some tree edges found in a dfs tree. (note that | S |= k ). Now, we can chose a subset of S, and to make an eulerian subgraph combining its elements, we apply the symmetric diference of them.