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.
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.