samadeep's blog

By samadeep, history, 10 months ago, In English

CSES Problem : Advanced Techniques Section

Is there a explanation and proof anyone can suggest me.

Link :Eulerian Subgraph

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.