CP-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/yosupo/Graph/eulerian_trail_directed.test.cpp
- View this file on GitHub
- Last update: 2025-04-30 09:35:53+07:00
- Problem: https://judge.yosupo.jp/problem/eulerian_trail_directed
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_directed"
#include "Misc/marco.hpp"
#include "Misc/debug.hpp"
const int INF=1e9;
const ll INFI=1e15;
//----------Author: Nguyen Ho Nam,UIT, Saigon-----------------
#include "Graph/Eulerian_trail.hpp"
int main(){
int t; cin>>t;
while(t--){
int n,m; cin>>n>>m;
eulerian_trail<int,true>et(n,m);
rep(i,m){
int u,v; cin>>u>>v;
et.add_edge(u,v,i);
}
if(!et.get_trail()){
cout<<"No"<<'\n';
}else{
cout<<"Yes"<<'\n';
rep(i,(int)et.path.size()){
cout<<et.path[i]<<(i+1<(int)et.path.size()?' ':'\n');
}
if(m==0){
cout<<'\n';
}else{
For(i,1,(int)et.edge_path.size()){
cout<<et.edge_path[i]<<(i+1<(int)et.edge_path.size()?' ':'\n');
}
}
}
}
}#line 1 "test/yosupo/Graph/eulerian_trail_directed.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_directed"
#line 2 "Misc/marco.hpp"
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ods;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ars(x) (x),(x+n)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define For(i,a,b) for (int i=(a); i<(b); i++)
#define rep(i,a) For(i,0,a)
#define rev(i,a,b) for (int i=(a); i>(b); i--)
#define FOR(i,a,b) for (int i=(a); i<=(b); i++)
#define REP(i,a) FOR(i,1,a)
#define REV(i,a,b) for (int i=(a); i>=(b); i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define FT ios_base::sync_with_stdio(false); cin.tie(nullptr);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using vi=vector<int>;
using vll = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
//template <class T>
//using ods =
// tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#line 1 "Misc/debug.hpp"
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
template<>
void __print(const vector<bool> &x) {int f = 0; cerr << '{'; for (size_t i = 0; i < x.size(); ++i) cerr << (f++ ? ", " : ""), __print(x[i]); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { __print(H); if (sizeof...(T)) cerr << ", "; dbg_out(T...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:"; dbg_out(__VA_ARGS__);
#line 4 "test/yosupo/Graph/eulerian_trail_directed.test.cpp"
const int INF=1e9;
const ll INFI=1e15;
//----------Author: Nguyen Ho Nam,UIT, Saigon-----------------
#line 2 "Graph/Eulerian_trail.hpp"
template<typename T,bool directed>
struct eulerian_trail {
int n, m, E, ptr = 0;
vector<int>head, link, to, eid, it_prev, it_cur;
vector<bool>used;
vector<T>path;
vector<int>edge_path;
eulerian_trail(int _n, int _m) : n(_n), m(_m) {
E = directed ? m : 2*m;
head.assign(n, 0);
link.assign(E+1, 0);
to.assign(E+1, 0);
eid.assign(E+1, 0);
used.assign(m, false);
it_prev.assign(n, 0);
it_cur.assign(n, 0);
}
void add_edge(int u, int v, int id) {
auto ins = [&](int U, int V, int EID){
int idx = ++ptr;
to[idx] = V;
eid[idx] = EID;
int old = head[U];
link[idx] = 0 ^ old;
if(old) link[old] ^= 0 ^ idx;
head[U] = idx;
};
if constexpr(directed) ins(u, v, id);
else { ins(u, v, id); ins(v, u, id); }
}
bool is_eulerian() {
if constexpr(directed) {
int start=0, end=0;
vector<int>in(n,0), out(n,0);
for(int u=0; u<n; u++){
int prev=0, cur=head[u];
while(cur){
out[u]++; in[to[cur]]++;
int nxt = prev ^ link[cur];
prev = cur; cur = nxt;
}
}
for(int i=0;i<n;i++){
int d = out[i] - in[i];
if(d==1) start++;
else if(d==-1) end++;
else if(d!=0) return false;
}
return (start==1&&end==1) || (start==0&&end==0);
} else {
int odd=0;
for(int u=0;u<n;u++){
int deg=0, prev=0, cur=head[u];
while(cur){
deg++;
int nxt = prev ^ link[cur];
prev = cur; cur = nxt;
}
if(deg%2) odd++;
if(odd>2) return false;
}
return odd==0 || odd==2;
}
}
T find_start() {
if constexpr(directed) {
vector<int>in(n,0), out(n,0);
for(int u=0;u<n;u++){
int prev=0, cur=head[u];
while(cur){
out[u]++; in[to[cur]]++;
int nxt=prev^link[cur];
prev=cur; cur=nxt;
}
}
for(int i=0;i<n;i++)
if(out[i]-in[i]==1) return i;
for(int i=0;i<n;i++)
if(out[i]>0) return i;
return 0;
} else {
for(int u=0;u<n;u++){
int deg=0, prev=0, cur=head[u];
while(cur){
deg++;
int nxt=prev^link[cur];
prev=cur; cur=nxt;
}
if(deg%2==1) return u;
}
for(int u=0;u<n;u++)
if(head[u]!=0) return u;
return 0;
}
}
bool get_trail(){
if(!is_eulerian()) return false;
for(int u=0;u<n;u++){
it_prev[u]=0;
it_cur[u]=head[u];
}
stack<pair<T,int>>st;
st.emplace(find_start(), -1);
while(!st.empty()){
auto [u, in_eid]=st.top();
int &prev=it_prev[u];
int &cur=it_cur[u];
while(cur){
int idx=cur;
int nxt=prev^link[idx];
prev=idx;
cur=nxt;
int e=eid[idx];
if(!used[e]){
used[e]=true;
st.emplace(to[idx], e);
goto CONTINUE;
}
}
path.push_back(u);
edge_path.push_back(in_eid);
st.pop();
CONTINUE: ;
}
if((int)path.size()!=m+1)
return false;
reverse(path.begin(),path.end());
reverse(edge_path.begin(),edge_path.end());
return true;
}
};
#line 8 "test/yosupo/Graph/eulerian_trail_directed.test.cpp"
int main(){
int t; cin>>t;
while(t--){
int n,m; cin>>n>>m;
eulerian_trail<int,true>et(n,m);
rep(i,m){
int u,v; cin>>u>>v;
et.add_edge(u,v,i);
}
if(!et.get_trail()){
cout<<"No"<<'\n';
}else{
cout<<"Yes"<<'\n';
rep(i,(int)et.path.size()){
cout<<et.path[i]<<(i+1<(int)et.path.size()?' ':'\n');
}
if(m==0){
cout<<'\n';
}else{
For(i,1,(int)et.edge_path.size()){
cout<<et.edge_path[i]<<(i+1<(int)et.edge_path.size()?' ':'\n');
}
}
}
}
}