#749 (div1+div2) E. Moment of Bloom(生成樹,歐拉回路)

Link

考慮

u

u

u點在

q

q

q次詢問中出現次數為奇數次

那必定無法使所有邊經過偶數次,因為

u的鄰邊被經過了奇數次,鄰邊就必然有一條邊被經過奇數次

考慮所有點在

q次詢問中都出現了偶數次,那麼建一顆生成樹

我們斷言,對于詢問

,

v

u,v

u,v隻需從

u在樹上走到

v

v即可滿足最後每條邊經過偶數次

考慮構造一張新圖,對于詢問

(

)

(u,v)

(u,v)在新圖上由點

u向點

v連一條邊

這樣新圖形成若幹個連通分量,考慮每個連通分量的度數都是偶數

這麼這個連通分量必定存在歐拉回路,從起點出發必定回到終點

是以在新圖的歐拉回路的路徑上由

u走到

v,對應的就在生成樹上從

v

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n,m,fa[maxn],L[maxn],R[maxn],in[maxn],vis[maxn],pre[maxn];
vector<int>vec[maxn],fg;
int find(int x){ return x==fa[x]?x:fa[x] = find( fa[x] );}
void dfs(int u,int s,int shu)
{
	if( u==s )	cout << shu << endl << u << " ";
	else
	{
		dfs( pre[u],s,shu+1 );
		cout << u << " ";
	}
}
void bfs(int s,int t)
{
	for(int i=1;i<=n;i++)	vis[i] = 0;	 
	queue<int>q; q.push( s );
	while( !q.empty() )
	{
		int u = q.front(); q.pop();
		if( u==t )
		{
			dfs( t,s,1 ); cout << endl;
			return;
		}
		for(auto v:vec[u] )
		{
			if( vis[v] )	continue;
			vis[v] = 1, pre[v] = u, q.push( v );
		}
	}
}
signed main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)	fa[i] = i;
	for(int i=1;i<=m;i++)
	{
		int l,r; cin >> l >> r;
		int fl = find( l ), fr = find( r );
		if( fl==fr )	continue;
		vec[l].push_back( r ); vec[r].push_back( l );
		fa[fl] = fr;
	}
	int q; cin >> q;
	for(int i=1;i<=q;i++)
	{
		cin >> L[i] >> R[i];
		in[L[i]]++; in[R[i]]++;
	}
	for(int i=1;i<=n;i++)
		if( in[i]&1 )	fg.push_back( i );
	if( fg.size() )	cout << "NO\n" << fg.size()/2;
	else
	{
		cout << "YES\n";
		for(int i=1;i<=q;i++)	bfs( L[i],R[i] );
	}
}