PROBLEM LINK:
Author: Mohammed Ehab
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta
DIFFICULTY:
HARD
PREREQUISITES:
DFS, Matching, Link-Cut Tree
PROBLEM:
You are given undirected simple graph with N vertices (numbered 1 through N) and M edges (numbered 1 through M). You want to colour the edges in red, green and yellow so that the graph would be perfectly balanced, which means that for each vertex, the number of red edges incident to it must be equal to the number of green edges incident to it.
Since you hate the colour yellow, his satisfaction with the graph will be greater when he uses fewer yellow edges. Can you help him choose how to colour the edges so that you remain in the surviving half of humanity?
QUICK EXPLANATION:
If in the given graph, each component has an even number of edges and each node has an even degree, then it is always possible to paint the edges in only two colours (Red and Green) such that the condition mentioned in the problem is satisfied. Now, we can achieve this graph by deleting some edges from the graph given in input (painting them in yellow) :
- If we encounter a node x with odd degree, we delete the edge between x and the neighbour of x with the minimum degree. Doing this greedily gives 20 points.
- Instead of removing the edge with the neighbour with the minimum degree, choose a neighbour y randomly and delete the edge between x and y. Keep doing this unless R becomes less than 2. This approach gives 40 points.
- For 100 points, create another graph, G’ with N disjoint nodes initially. Move edges from input graph G to G’ as long as G is not matching. Whenever we find an even circuit in G’, color it with Red and Green alternately and remove it from G’. It is easy to show that if G is matching, all the edges in G should be colored in Yellow.
EXPLANATION:
Lemma 1: If G is a matching, all its edges will be covered in yellow.
Proof: If a graph is matching, each of its nodes will have degree at most 1. Now, if a node has degree 1 and we paint the only edge associated with Red, we will have to compensate for this action by painting another edge associated with this node in Green, but this won’t be possible since this node has a degree 1. Therefore, this edge must be painted in Yellow. This holds for all the edges in a matching graph.
Lemma 2: If there exists an even circuit, we can color its edges in Red and Green alternately.
Proof: For any particular vertex in the circuit, there will be two edges. Simply put, if we traverse the circuit once, we enter each node once and leave each node once. So if we paint the entering edge and leaving edge in opposite colors, it evens out the net effect for that particular vertex, or that vertex is still perfectly balanced.
Lemma 3: Even if an even circuit is removed, the graph’s balance won’t be affected.
Proof: If an even circuit is removed, it certainly means that the degree of each vertex in the circuit is reduced by 2. It has zero net effect on the balance of the graph because out of the 2 removed edges for each node, we can paint one in Red and the other in Green, which would help keep the balance same as before for that vertex, and in turn for the entire graph.
Consider the graph given in input as G. Create another graph (which would be a forest at any point of time) G’ with all the vertices as in G, but has no edges in it initially.
Let’s process the edges from a particular vertex (say x) one by one in the following manner :
- If both the endpoints of the edge belong to different components in G’, move this edge from G to G’. Formally, connect these endpoints in G’ as well, so that both are in the same component in G’ now and delete this edge from G.
- If both endpoints of this edge belong to the same component :
- If the distance between both of them in G’ is odd, then connecting this edge will make this an even circuit. So now we can remove the even circuit from G’ and color its edges with Red and Green alternately. If there exists an edge x to y which we previously retained for later usage, and both endpoints of the retained edge are not in the same component in G’, then we connect them in G’ and remove this edge from G, thereby deleting the retained edge.
- If the distance between both the endpoints in G’ is not odd, we will keep this edge (say x to y) for later use if we are not retaining an edge already. Note that connecting the endpoints of this edge in G’ forms an odd length cycle, which is not suitable for painting.
- If we are retaining an edge already, and both endpoints of the current edge are in the same component such that the distance between them is even, then we can say that we can have another odd length cycle in G’ if we connect the endpoints of the current edge. Now, we have one odd length cycle formed due to the current edge, say C_1, and another odd length cycle formed due to the previously retained edge, say C_2. Also, there exists one common vertex x among the two cycles, C_1 and C_2. So, we can say that both the odd length cycles C_1 and C_2 meet at x to form an even length cycle. Once we have found this even length cycle in G’, we can simply paint its edges in Red and Green alternately, and remove it from G’.
If we do these steps for all vertices from 1 through N, in such a manner that G’ is a forest at any point of time, we will certainly end up with G as a matching, i.e., each vertex has a degree less than or equal to 1.
At the end of these steps, we will end up with G as a matching, and it can be said with the help of Lemma 1 that the edges remaining in G will be colored in Yellow.
Note that since G is always a forest, we can speed up the operations to O(mlog(n)) by using Link/Cut tree.
TIME COMPLEXITY:
TIME: O(N logN)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005];
map<pair<int,int>,int> idx;
int p[100005],ch[2][100005];
bool flip[100005],del[300005];
int sz[100005],ans[300005];
void push(int node)
{
if (flip[node])
{
flip[node]=0;
swap(ch[0][node],ch[1][node]);
if (ch[0][node])
flip[ch[0][node]]^=1;
if (ch[1][node])
flip[ch[1][node]]^=1;
}
}
void recalc(int node)
{
push(ch[0][node]);
push(ch[1][node]);
sz[node]=1+sz[ch[0][node]]+sz[ch[1][node]];
}
int side(int node)
{
if (!p[node])
return -2;
if (ch[0][p[node]]==node)
return 0;
if (ch[1][p[node]]==node)
return 1;
return -1;
}
void attach(int par,int node,int s)
{
if (node)
p[node]=par;
if (s>=0)
ch[s][par]=node;
}
void rotate(int node)
{
int s=side(node),par=p[node];
attach(p[par],node,side(par));
attach(par,ch[!s][node],s);
attach(node,par,!s);
recalc(par);
recalc(node);
}
void splay(int node)
{
while (side(node)>=0 && side(p[node])>=0)
{
push(p[p[node]]);
push(p[node]);
push(node);
rotate((side(node)==side(p[node]))? p[node]:node);
rotate(node);
}
if (side(node)>=0)
{
push(p[node]);
push(node);
rotate(node);
}
push(node);
}
void access(int node)
{
int o=node,cur=0;
while (node)
{
splay(node);
ch[1][node]=cur;
recalc(node);
cur=node;
node=p[node];
}
splay(o);
}
void reroot(int node)
{
access(node);
flip[node]^=1;
access(node);
}
int dep(int node)
{
access(node);
return sz[ch[0][node]];
}
int find(int node)
{
access(node);
while (ch[0][node])
{
node=ch[0][node];
push(node);
}
access(node);
return node;
}
void link(int x,int y)
{
reroot(x);
access(y);
attach(x,y,0);
recalc(x);
}
void cut(int x,int y)
{
reroot(x);
access(y);
p[ch[0][y]]=0;
ch[0][y]=0;
recalc(y);
}
int parent(int node)
{
access(node);
node=ch[0][node];
push(node);
while (ch[1][node])
{
node=ch[1][node];
push(node);
}
access(node);
return node;
}
int go(int a,int b,int c2)
{
int c1=1,d1=dep(a),d2=dep(b);
vector<pair<int,int> > c;
while (a!=b)
{
if (d1<d2)
{
swap(a,b);
swap(c1,c2);
swap(d1,d2);
}
int p=parent(a);
ans[idx[{p,a}]]=c1;
c1*=-1;
c.push_back({a,p});
a=p;
d1--;
}
for (auto e:c)
cut(e.first,e.second);
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n,m;
scanf("%d%d",&n,&m);
idx.clear();
for (int i=1;i<=n;i++)
{
v[i].clear();
p[i]=0;
ch[0][i]=ch[1][i]=0;
flip[i]=0;
sz[i]=1;
}
for (int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
idx[{a,b}]=i;
idx[{b,a}]=i;
ans[i]=0;
del[i]=0;
}
for (int a=1;a<=n;a++)
{
int b=-1;
for (int c:v[a])
{
int i=idx[{a,c}];
if (!del[i] && !ans[i])
{
if (find(a)!=find(c))
{
link(a,c);
del[i]=1;
}
else if (dep(a)%2!=dep(c)%2)
{
ans[i]=-1;
go(a,c,1);
if (b!=-1 && find(a)!=find(b))
{
link(a,b);
del[idx[{a,b}]]=1;
b=-1;
}
}
else if (b==-1)
b=c;
else
{
ans[idx[{a,b}]]=-1;
ans[i]=1;
go(b,c,-1);
b=-1;
}
}
}
}
for (int i=0;i<m;i++)
printf("%d\n",ans[i]);
}
}
Tester's Solution
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define sz(a) (int)(a.size())
using namespace std;
const int MAX = 100005;
int occ[MAX][2];
int banned[3 * MAX];
int color[3 * MAX];
int ptr[MAX];
vector<pair<int , int> > g[MAX];
pair<int, int> getNext(int u)
{
while(ptr[u] < sz(g[u]))
{
if(banned[g[u][ptr[u]].y])
{
ptr[u]++;
continue;
}
banned[g[u][ptr[u]].y] = 1;
return g[u][ptr[u]];
}
return {-1 , -1};
}
void dfs(int u)
{
vector<int> stV = {u};
vector<int> stE;
occ[u][0] = 0;
while(!stV.empty())
{
int u = stV.back();
pair<int, int> edge = getNext(u);
if(edge.x == -1)
{
stV.pop_back();
if(sz(stE))
stE.pop_back();
occ[u][sz(stV) % 2] = -1;
continue;
}
if(occ[edge.x][sz(stV) % 2] != -1)
{
color[edge.y] = (((sz(stE) + 1) % 2) == 1) ? 1 : -1;
int oc = occ[edge.x][sz(stV) % 2] + 1;
while(sz(stV) > oc)
{
int v = stV.back();
stV.pop_back();
occ[v][sz(stV) % 2] = -1;
color[stE.back()] = ((sz(stE) % 2) == 1) ? 1 : -1;
stE.pop_back();
}
continue;
}
occ[edge.x][sz(stV) % 2] = sz(stV);
stV.pb(edge.x);
stE.pb(edge.y);
}
occ[u][0] = -1;
}
int main()
{
memset(occ, -1 , sizeof occ);
int T;
cin >> T;
int sumN = 0 , sumM = 0;
while(T--)
{
int n, m;
cin >> n >> m;
assert(1 <= n && n <= 1e5);
assert(0 <= m && m <= 3e5);
sumN += n;sumM += m;
assert(sumN <= 3e5);
assert(sumM <= 9e5);
set<pair<int,int> > edges;
for(int i = 0; i < m; i++)
{
int u , v;
cin >> u >> v;
if(u > v)
swap(u , v);
assert(u != v);
assert(1 <= u && u <= n);
assert(1 <= v && v <= n);
edges.insert({u , v});
u--;v--;
g[u].pb({v , i});
g[v].pb({u , i});
}
assert(sz(edges) == m);
for(int i = 0; i < n; i++)
{
dfs(i);
}
for(int i = 0; i < m; i++)
{
cout << color[i] << endl;
banned[i] = color[i] = 0;
}
for(int i = 0; i < n; i++)
{
g[i].clear();
ptr[i] = 0;
}
}
return 0;
}