3748 . [模板題] Eulerian Trail (Directed)
TopCoder
Tags
Description
This problem has $T$ cases.
You are given a directed graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is directed from $u_ i$ to $v_ i$.
An eulerian trail of $G$ is a pair of sequence of vertices $(v_ 0,\ldots,v_ M)$ and sequence of edges $(e_ 0,\ldots,e_ {M-1})$ satisfying following conditions.
- $(e_ 0,\ldots,e_ {M-1})$ is a permutation of $(0, \ldots, M-1)$.
- For $0\leq i < M-1$, the edge $e_ i$ is directed from $v_ i$ to $v_ {i+1}$.
Determine if an eulerian trail of $G$ exists, and output if it exists.
Input Format
$T$
$N$ $M$
$u_ 0$ $v_ 0$
$\vdots$
$u_ {M-1}$ $v_ {M-1}$
$N$ $M$
$u_ 0$ $v_ 0$
$\vdots$
$u_ {M-1}$ $v_ {M-1}$
$\vdots$
Output Format
If there exists no eulerian trail, print No. Otherwise, print an eulerian trail in the following format.
Yes
$v_ 0$ $\ldots$ $v_ {M}$
$e_ 0$ $\ldots$ $e_ {M-1}$
Sample Input 1
3 4 7 0 1 2 0 0 2 3 0 1 3 2 3 3 3 4 6 0 1 2 0 0 3 1 2 3 1 2 3 6 10 0 3 1 2 4 0 5 1 4 4 2 3 3 1 3 2 1 4 1 5
Sample Output 1
Yes 2 0 1 3 0 2 3 3 1 0 4 3 2 5 6 No Yes 1 2 3 1 5 1 4 4 0 3 2 1 5 6 9 3 8 4 2 0 7
Sample Input 2
6 10 0 10 1 0 1 10 1 4 4 10 2 4 4 5 5 10 2 3 6 6 3 10 2 3 6 3 6
Sample Output 2
Yes 0 Yes 0 1 0 Yes 4 4 0 No Yes 3 6 3 0 1 No
Hints
- $1 \leq T \leq 10^ {5}$
- $1 \leq N \leq 2 \times 10^ {5}$
- $0 \leq M \leq 2 \times 10^ {5}$
- $0 \leq u_ i, v_ i \lt N$
- The sum of $N$ over all test cases does not exceed $2 \times 10^ {5}$.
- The sum of $M$ over all test cases does not exceed $2 \times 10^ {5}$.
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|