颠倒原理 / reverse
题目描述
\(GreenDuck\)想学习转置原理，但由于它太难了，因此他转而学习更为简单的和图的染色有密切联系的“颠倒原理”\((reverse principle)\)。
颠倒原理中有个重要的操作叫做“颠倒操作”。对于一个无向连通图\(G\)，其节点要么是黑色要么是白色。“颠倒操作”每次会选择\(G\)的一条无向边\((u, v)\)，将\(u, v\)这两个点的颜色颠倒。也就是说，如果\(u\)是白色的，那么将\(u\)变为黑色的；如果\(u\)是黑色的，那么将u变成白色的。对\(v\)也同样处理。如果能通过有限次操作使得这张图所有点都变为黑色，那么这张图便是“可颠倒”的。
现在\(GreenDuck\)有一个具有\(n\)个点，\(m\)条边的无向连通图，一开始所有点均为白色。他想知道
这个图是否是“可颠倒”的。请你告诉他是否是“可颠倒”的，如果是，那么输出一种方案。
输入格式
第一行两个正整数\(n, m\)，表示图的点数和边数。
接下来m行，每行两个正整数\(x, y\)，表示一条边的两个端点。
输出格式
如果图不是“可颠倒”的，输出一行一个字符串("\(No\)")(不要双引号)。
否则，先输出一行一个字符串("\(Yes\)")，再在第二行输出进行“颠倒操作”的边的个数\(k\)，最后\(k\)行，每行输出一条边的两个端点。
注意，请严格按照格式输出。同时，如果你输出的边不存在，或者出现不止一遍，那么该测试点将不予评分。一条边两个端点的顺序没有要求。边的输出顺序也没有要求。
样例1输入
4 3
1 2
2 3
2 4
样例1输出
Yes
3
2 1
2 4
2 3
样例1解释
操作\((2, 1)\)会将点\(1, 2\)染成黑色，操作\((2, 4)\)会将点\(2\)染成白色，将点\(4\)染成黑色，操作\((2, 3)\)会将点\(2, 3\)染成黑色。
样例2输入
3 3
1 2
2 3
3 1
样例2输出
No
数据范围
对于所有测试点，不存在重边或自环
对于\(100%\)的数据，\(n, m <= 300000\)。
solution
30pts
我们可以发现每条边最多染色一次。
所以\(O(2 ^ m)\)枚举每一条边是否染色
50pts
当图是一条边或一条链时，结论比较显然，如果点的个数是单数时，输出\(No\)，否则输出\(Yes\)。
70pts
我们考虑\(m == n - 1\)这个特殊性质。
引理：n为奇数时一定不可能全变黑
证明
当我们进行颠倒操作时，可以分为以下几种情况：
1.两点均为白/黑 => 黑+2，白-2 or 白+2，黑+2。 奇偶不变
2.两点一白一黑 => 相当于两点交换颜色，奇偶不变
所以奇偶不变，也就不可能全变黑。
所以当图是树时，\(n\)是奇数时无解，考虑\(n\)是偶数时，用\(w_i\)记录\(i\)点的颜色，跑一遍\(dfs\),在回溯时更新。
my code
考场上想出来的70分做法，其实已经很接近正解了。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m;
bool flag, v[N];
vector <int> g[N];
int d[N], t[N], cnt1, cnt2, s, c[N], tot, w[N], idx;
struct node{
int u, v;
}f[N], ans[N];
bool check(int sum)
{
for(int i = 1;i <= n;i++) d[i] = 0;
for(int i = 1;i <= sum;i++)
{
d[ans[i].u]++;
d[ans[i].v]++;
}
for(int i = 1;i <= n;i++)
{
if(d[i] % 2 == 0) return 0;
}
return 1;
}
void dfs(int u, int f)
{
v[u] = 1;
c[++tot] = u;
for(int i = 0;i < g[u].size();i++)
{
int j = g[u][i];
if(v[j]) continue;
dfs(j, u);
}
}
void dg(int dep, int sum)
{
if(dep > m)
{
if(flag == 0 && check(sum) == true)
{
flag = 1;
cout<<"Yes"<<"\n";
cout<<sum<<"\n";
for(int i = 1;i <= sum;i++)
{
cout<<ans[i].u<<" "<<ans[i].v<<"\n";
}
}
}
else
{
dg(dep + 1, sum);
ans[sum + 1] = f[dep];
dg(dep + 1, sum + 1);
}
}
void dfs1(int u, int f)
{
for(int i = 0;i < g[u].size();i++)
{
int j = g[u][i];
if(j == f) continue;
dfs1(j, u);
if(w[j] == 0)
{
w[j] ^= 1, w[u] ^= 1;
ans[++idx] = {j, u};
}
}
}
int main()
{
freopen("reverse.in", "r", stdin);
freopen("reverse.out", "w", stdout);
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;i++)
{
int x, y;
cin >> x >> y;
f[i] = {x, y};
t[x]++;
t[y]++;
g[x].push_back(y);
g[y].push_back(x);
}
if(m <= 20)
{
dg(1, 0);
if(flag == 0) cout<<"No"<<"\n";
return 0;
}
for(int i = 1;i <= n;i++)
{
if(t[i] == 1)
{
s = i;
cnt1++;
}
if(t[i] == 2) cnt2++;
}
if(cnt1 + cnt2 == n && cnt1 == 2)
{
if(n % 2 == 0)
{
dfs(s, -1);
cout<<"Yes"<<"\n";
cout<<n / 2<<"\n";
for(int i = 1;i <= n;i+=2)
{
cout<<c[i]<<" "<<c[i + 1]<<"\n";
}
}
else cout<<"No"<<"\n";
return 0;
}
if(cnt2 == n)
{
if(n % 2 == 0)
{
dfs(1, -1);
cout<<"Yes"<<"\n";
cout<<n / 2<<"\n";
for(int i = 1;i <= n;i+=2)
{
cout<<c[i]<<" "<<c[i + 1]<<"\n";
}
}
else cout<<"No"<<"\n";
return 0;
}
if(m == n - 1)
{
if(n % 2 == 0)
{
dfs1(1, -1);
cout<<"Yes"<<"\n";
cout<<idx<<"\n";
for(int i = 1;i <= idx;i++)
{
cout<<ans[i].u<<" "<<ans[i].v<<"\n";
}
}
else cout<<"No"<<"\n";
return 0;
}
cout<<"No"<<"\n";
return 0;
}
100pts
和树判定的方法一样，不过求一颗生成树即可。
std code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int h[N], e[N << 1], ne[N << 1], idx;
int st[N], color[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int n, m;
vector <pair<int, int>> res;
void dfs(int u, int f)
{
st[u] = 1;
for(int i = h[u]; ~i;i = ne[i])
{
int j = e[i];
if(st[j]) continue;
dfs(j, u);
}
if(!color[u] && f != -1)
{
res.push_back({u, f});
color[f] = !color[f];
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
while(m--)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
if(n % 2)
{
puts("No");
return 0;
}
dfs(1, -1);
printf("Yes\n%d\n", res.size());
for(int i = 0;i < res.size();i++)
printf("%d %d\n",res[i].first, res[i].second);
}