洛涅树林WA0 求调

[赵泽龙]

分别考虑是奇数的情况和偶数的情况。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
struct edge{int nxt,to;}e[maxn << 1];
int head[maxn],tot;
void add_edge(int u,int v)
{
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].to = v;
}

namespace DSU
{
	int fa[maxn];
	int Find(int u){return fa[u] == u ? u : fa[u] = Find(fa[u]);}
	void merge(int u,int v){fa[Find(v)] = Find(u);}
}using namespace DSU;

int n,m,Cnt;
bool vis[maxn];
map<pair<int,int>,int> mp;

namespace odd
{
	int F[maxn],deg[maxn],cnt[maxn];
	void dfs(int u)
	{
		Cnt++;vis[u] = 1;
		for(int i = head[u];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(vis[v])continue;
			dfs(v);
		}
	}
	
	void dfs2(int u,int fa)
	{
		vis[u] = 1;
		for(int i = head[u];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(vis[v])continue;
			if(Find(u) != Find(v))merge(u,v),deg[u]++,F[v] = u;
			dfs2(v,u);
		}
	}
	
	void solve()
	{
		memset(vis,0,sizeof(vis));
		for(int i = 1;i <= 2 * n;i++)
		{
			if(!vis[i])
			{
				Cnt = 0;dfs(i);
				if(Cnt & 1)return ;
			}
		}
		memset(vis,0,sizeof(vis));
		for(int i = 1;i <= 2 * n;i++)fa[i] = i;
		for(int i = 1;i <= 2 * n;i++)
		{
			if(!vis[i])dfs2(i,0);
		}
		vector<int> ans;
		queue<int> q;
		for(int i = 1;i <= 2 * n;i++)if(!deg[i])q.push(i);
		while(!q.empty())
		{
			int u = q.front();q.pop();
			if(cnt[u] % 2 == 0)
			{
				if(F[u] > u)ans.push_back(mp[make_pair(u,F[u] - n)]);
				else ans.push_back(mp[make_pair(F[u],u - n)]);
				cnt[F[u]]++;
			}
			if(!--deg[F[u]])q.push(F[u]);
		}
		if(ans.size() == 0)return ;
		cout << "OUI\n" << ans.size() << '\n';
		for(int i = 0;i < ans.size();i++)cout << ans[i] << " ";
		exit(0);
	}
}

namespace even
{
	int deg[maxn];
	bool vis[maxn];
	vector<int> ans;
	int lst;
	void dfs(int u)
	{
		vis[u] = 1;lst = u;
		for(int i = head[u];i;i = e[i].nxt)
		{
			int v = e[i].to;
			if(vis[v])continue;
			if(deg[v] <= 1)continue;
			if(v > u)ans.push_back(mp[make_pair(u,v - n)]);
			else ans.push_back(mp[make_pair(v,u - n)]);
			dfs(v);
		}
	}
	void solve()
	{
		queue<int> q;
		for(int i = 1;i <= 2 * n;i++)
		{
			if(deg[i] == 1)
			{
				q.push(i);
				vis[i] = 1;
			}
		}
		while(!q.empty())
		{
			int u = q.front();q.pop();
			for(int i = head[u];i;i = e[i].nxt)
			{
				int v = e[i].to;
				if(--deg[v] <= 1 && !vis[v])
				{
					q.push(v);vis[v] = 1;
				}
			}
		}
		memset(vis,0,sizeof(vis));
		int first = 0;
		for(int i = 1;i <= 2 * n;i++)if(deg[i] > 1)first = i;
		if(first == 0)return ;
		dfs(first);
		if(lst > first)ans.push_back(mp[make_pair(first,lst - n)]);
		else ans.push_back(mp[make_pair(lst,first - n)]);
		if(ans.size() == 0)return ;
		cout << "OUI\n" << ans.size() << '\n';
		for(int i = 0;i < ans.size();i++)cout << ans[i] << " ";
		exit(0);
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int u,v;cin >> u >> v;
		add_edge(u,v + n);
		add_edge(v + n,u);
		even::deg[v + n]++;even::deg[u]++;
		mp[{u,v}] = i;
	}
	odd::solve();
	even::solve();
	cout << "NON";
	return 0;
}