The inversion principle / reverse
Time limit: 1000ms
Space limit: 512MB
Title Description
\(GreenDuck\)He wanted to learn the principle of transposition, but since it was too difficult, he switched to the simpler "principle of inversion", which is closely related to the coloring of diagrams.\((reverse principle)\)。
There is an important operation in the inversion principle called the "inversion operation". For an undirected connected graph\(G\)The nodes are either black or white. "The Upside Down operation selects the\(G\)an undirected edge of a manifold (math.)\((u, v)\)will\(u, v\)The colors of these two dots are reversed. That is, if the\(u\)is white, then will\(u\)becomes black; if\(u\)is black, then will u turn white. For\(v\)The same is done. A graph is "invertible" if it can be made black at all points in a finite number of operations.
present .\(GreenDuck\)There's one with a\(n\)points.\(m\)An undirected connectivity graph with bar edges, where all points are white at the beginning. He wants to know
Is this diagram "invertible". Please tell him if it is "invertible", and if so, output a solution.
input format
Two positive integers in the first row\(n, m\), indicating the number of points and sides of the graph.
The next m rows are two positive integers each.\(x, y\), denotes the two endpoints of a side.
output format
If the graph is not "invertible", output a line with a string ("\(No\)") (no double quotes).
Otherwise, first output a line a string ("\(Yes\)"), and then in the second line output the number of edges that were "inverted".\(k\)Finally\(k\)rows, each outputting the two endpoints of an edge.
Note that please follow the formatting of the output strictly. Also, if you output an edge that does not exist, or appears more than once, that test point will not be graded. There is no requirement for the order of the two endpoints of an edge. The order in which the edges are output is also not required.
Sample 1 Input
4 3
1 2
2 3
2 4
Sample 1 Output
Yes
3
2 1
2 4
2 3
Sample 1 Explanation
manipulate\((2, 1)\)checkpoint\(1, 2\)Dyeing black, operation\((2, 4)\)will checkmate\(2\)Dye the dots white.\(4\)Dyeing black, operation\((2, 3)\)will checkmate\(2, 3\)Dyed black.
Sample 2 Input
3 3
1 2
2 3
3 1
Sample 2 Output
No
Data range
For all test points, there are no heavy edges or self-loops
insofar as\(100%\)of the data.\(n, m <= 300000\)。
solution
30pts
We can find each edge colored at most once.
the reason why\(O(2 ^ m)\)Enumerate whether each edge is colored
50pts
The conclusion is more obvious when the graph is an edge or a chain, and the output if the number of points is singular\(No\)Otherwise output\(Yes\)。
70pts
We consider\(m == n - 1\)This particular nature.
Lemma: It must not be possible for n to be all black when n is an odd number
show that
When we perform an inversion operation, it can be categorized as follows:
1. Both points are white/black => black+2, white-2 or white+2, black+2. Parity remains the same.
2. Two points, one white and one black => Equivalent to two points exchanging colors, parity unchanged
So the parity stays the same and it can't be all black.
So when the graph is a tree\(n\)is unsolvable for odd numbers, consider\(n\)When it is an even number, use\(w_i\)record (in sports etc)\(i\)Dots of color, run it through\(dfs\), updated on backtracking.
my code
The 70 mark approach that you come up with in the exam room is actually pretty close to the right solution.
#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("", "r", stdin);
freopen("", "w", stdout);
ios :: sync_with_stdio(0);
(0);
(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
Same method as tree determination, but just ask for a spanning tree.
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", ());
for(int i = 0;i < ();i++)
printf("%d %d\n",res[i].first, res[i].second);
}