EVEDG - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Fang Lixing
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

EASY

PREREQUISITES:

Math, Graph Theory

PROBLEM:

Given an undirected graph G=(V,E), partition the vertex set V into as few as possible (disjoint) subsets, such that the induced subgraph of each subset contains an even number of edges.

QUICK EXPLANATION:

  • If the graph itself has an even number of edges, we can “divide” it into one set;
  • Otherwise, |E| must be odd. If the degree of some vertex v is odd, then we partition V into \{v\} and V-\{v\};
  • Otherwise we pick any edge (u,v)\in E, and partition V into \{u\}, \{v\} and V-\{u,v\}.

EXPLANATION:

It’s easy to see that if the graph itself contains an even number of edges, then we can “divide” it into one set and K=1. The number of edges belonging to this set is even.

If the graph contains an odd number of edges, then there are two cases:

Case 1: If there is a vertex v whose degree \deg(v) is odd, then we can partition the vertices into K=2 sets: the first set is \{v\}, and the second set is V-\{v\}. The number of edges in the first set is 0, and the number of edges in the second set is |E|-\deg(v). Since both |E| and \deg(v) is odd, this solution is valid.

Case 2: Suppose the degree of every vertex is even. It’s impossible to partition the vertices into 2 sets, such that every set has an even number of edges.

Proof

Assume, for the sake of contradiction, that V=X\cup Y is such a partition.

We denote E[X] as the set of edges in the induced subgraph of X, and E[Y] as the set of edges in the induced subgraph of Y. We also let E[X,Y] be the set of edges between X and Y. Let’s count the sum of degrees of vertices in X, and denote it by S, i.e. S=\sum_{x\in X}\deg(x). Since every vertex has even degree, S should be an even number. However

  • For each edge in E[X], it’s counted twice in S;
  • For each edge in E[Y], it doesn’t affect S at all;
  • For each edge in E[X,Y], it’s counted once in S.

Therefore the parity of S should be equal to the parity of |E[X,Y]|. Since there are an odd number of edges in G, but an even number of edges in both E[X] and E[Y], we know that |E[X,Y]| is odd, a contradiction. QED.

Can we do it in three sets? The answer is YES! We pick any edge e=(u,v) that’s in E, and partition V into three sets \{u\},\{v\} and V-\{u,v\}.

We still need to prove that V-\{u,v\} contains an even number of edges. The edges not in the induced subgraph of V-\{u,v\} are either the edges incident to u, or the edges incident to v. Since both \deg(u) and \deg(v) are even, it seems that there are an even number of edges not in V-\{u,v\}. However, we counted the edge (u,v) twice! If we subtract this edge, we know that the number of edges not in V-\{u,v\} is odd. And since G has an odd number of edges, V-\{u,v\} contains an even number of edges, and we’re done.

Time complexity is O(N+M).

ALTERNATE EXPLANATION:

Please feel free to share your approaches :slight_smile:

SOLUTIONS:

Setter's Solution
#include <cstdio>
#include <algorithm>
int read() {
  int w = 1, q = 0, ch = ' ';
  for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
  return q * w;
}
const int N = 100010;
int n, m, deg[N], u, v;
void Main() {

  // answer <= 3

  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    deg[i] = 0;
  }
  for (int i = 1; i <= m; i++) {
    u = read();
    v = read();
    deg[u] ^= 1;
    deg[v] ^= 1;
  } // read, and calculate the parity of degree


  if (!(m & 1)) {
    putchar('1'), putchar('\n');
    for (int i = 1; i <= n; i++) {
      putchar('1'), putchar(' ');
    }
    putchar('\n');
    return;
  } // the whole graph is okay, answer = 1


  for (int i = 1; i <= n; i++) {
    if (deg[i]) {
      putchar('2'), putchar('\n');
      for (int j = 1; j <= n; j++) {
        if (j != i) {
          putchar('1'), putchar(' ');
        } else {
          putchar('2'), putchar(' ');
        }
      }
      putchar('\n');
      return;
    }
  } // if a vertex got odd degree, divide it, answer = 2

  
  putchar('3'), putchar('\n');
  for (int i = 1; i <= n; i++) {
    if (i == u) {
      putchar('2'), putchar(' ');
    } else if (i == v) {
      putchar('3'), putchar(' ');
    } else {
      putchar('1'), putchar(' ');
    }
  }
  putchar('\n'); // divide the end point of any edge, answer = 3

  
}
int main() {
  int T = read();
  while (T--) {
    Main();
  }
  return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
void pi(int x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}

int u[102020], v[102020], deg[102020];
void doit() {
  int n, m, i, j;
  gi(n); gi(m);
  for (i = 1; i <= n; i++) deg[i] = 0;
  for (i = 1; i <= m; i++) {
    gi(u[i]); gi(v[i]);
    deg[u[i]]++; deg[v[i]]++;
  }
  if (~m & 1) {
    pi(1); putchar('\n');
    for (i = 1; i <= n; i++) pi(1), putchar(' ');
  } else {
    for (i = 1; i <= n; i++) if (deg[i] & 1) break;
    if (i <= n) {
      pi(2); putchar('\n');
      for (j = 1; j <= n; j++) {
        if (j == i) pi(2); else pi(1);
        putchar(' ');
      }
    } else {
      pi(3); putchar('\n');
      for (j = 1; j <= n; j++) {
        if (j == u[1]) pi(2);
        else if (j == v[1]) pi(3);
        else pi(1);
        putchar(' ');
      }
    }
  }
  putchar('\n');
}

int main() {int t; gi(t); while (t--) doit(); return 0;}
11 Likes

I used this logic but couldn’t pass 2nd task of subtask 1.Can anyone tell me which case i was missing.

The question was a little ambiguous regarding the deletion of edges. Also, I did not get that k could be 1. The problem should have mentioned the lower limit on k. Just sharing my thoughts on the question!

I also didn’t knew the lower limit of value of k. But some guy asked it in the comments in div2.

The graphs can be disconnected on their own aswell,
Example
1 2
2 3
3 4
4 1
5 6
6 7
7 5
Now you cannot remove 1 node from 1st subgraph and 1 from 2nd subgraph, you have to remove both the nodes from the same subgraph. So you have to do dfs traversal on any node of that graph and get the node list and then you can set any 2 nodes to different sets

Is this valid?

2 Likes

Wow.you explained it without any words.Damn i made so many submission just couldn’t guess this case.

But does that mean editorial is incorrect?

Yes that is valid and I missed that .

The editorial implemented the logic differently,I havent checked out their solution.

The question said that you have to minimize K. Does not make sense to exclude K=1 here.

3 Likes

Editorial is correct. The problem nowhere mentioned that the induced subgraph has to be connected. You get 2 connected components, one with 3 edges, and other with 1 edge and hence a total of 4 edges.

2 Likes

My approach:
Answer can be either 1,2 or 3
How?

If the number of edges is even
then k=1

Else if number of edges is odd then there are two cases:

If a node exists with ODD number of edges, removing that vertex alone makes number of remaining edges EVEN.(ODD-ODD=EVEN). So there are two sets: removed vertex and remaining verices.

If there is no node with ODD number of edges, then two adjacent nodes will form two separate sets and remaining nodes the third set. Removing two nodes with even number of Edges having a common edge is actually removing ODD numbers of Edges(Even+Even-1). Which makes remaining count Even (ODD-ODD=EVEN).

Time complexity is O(E)

hope it helps.

8 Likes

I used the same logic but still got some subtasks wrong.
I couldn’t find anything I could’ve missed. Any help would be highly appreciated!

This is the code I used for the third case (where k = 3):

for(int i = 0; i < n; i++) { // i = no of nodes
    if(graph[i].size() == 0) continue; // the node to be removed must have a neighbour
    k = 3;
    subgraph[i] = 2; // The first node becomes subgraph 3
    subgraph[*graph[i].begin()] = 3; // second node becomes subgraph 3 & remaining all are in subgraph 1 by default
    break;
}

Is there an issue with this?

My entire solution can be found here: https://www.codechef.com/viewsolution/27327101

You have a bug at reading edge list.
Your code:

graph[u-1].push_back(v);
graph[v-1].push_back(u);

Correct code:

graph[u-1].push_back(v-1);
graph[v-1].push_back(u-1);

1 Like
 //problem in this solution ?
import java.lang.reflect.Array;
import java.util.*; import java.io.*; import java.math.*;

public class Main {
static Reader scan = new Reader(); static Scanner scan2 = new Scanner(System.in);
static int MAX = 1111111, MAX_BUCKET = 111;
public static void main(String[] args) throws IOException{

    int t = scan.nextInt();


    while(t-->0){
        int n = scan.nextInt(), m = scan.nextInt();
        HashMap<Integer, HashMap<Integer, Integer>> g = new HashMap<>();
        for(int i=0;i<n; i++){g.put(i, new HashMap<>());}
        for (int i=0; i<m;i++){
            int src = scan.nextInt()-1, des = scan.nextInt()-1;
            g.get(src).put(des,1); g.get(des).put(src,1);
        }
        int[] answer = new int[n]; boolean visited[] = new boolean[n];
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true; pair temp = bfs(i,visited,g);
                if((temp.size&1) == 0){
                    for(int node : temp.nodes){answer[node] = 1;}
                }else{
                    boolean od = false; int fl = -1;
                    for(int node : temp.nodes){
                        if((g.get(node).size()&1) != 0){od= true; fl = node;}
                        answer[node] = 1;
                    }
                    if(od){
                        answer[fl] = 2;
                    }else{
                        int a = temp.nodes.get(0), b = g.get(a).entrySet().iterator().next().getKey();
                        answer[a] = 2; answer[b] = 3;
                    }
                }
            }
        }
        for(int u : answer){ System.out.print(u+" "); }System.out.println();
    }

}

public static pair bfs(int src, boolean[] visited, HashMap<Integer, HashMap<Integer, Integer>> g){
    LinkedList<Integer> queue = new LinkedList<>(); queue.addFirst(src);
    pair answer = new pair(); answer.nodes.add(src); answer.size = g.get(src).size();
    while(!queue.isEmpty()){
        int curr = queue.removeLast();
        for(int ch : g.get(curr).keySet()){
            if(!visited[ch]){visited[ch]= true;queue.addLast(ch); answer.nodes.add(ch); answer.size+=g.get(ch).size();}
        }
    }
    answer.size = (answer.size>>1);
    return answer;
}


static class pair{
    ArrayList<Integer> nodes = new ArrayList<>(); int size=0;
    public String toString(){
        return nodes+" "+size;
    }
}


static class Reader
{
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1)
        {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
        {
            ret = ret * 10 + c - '0';
        }  while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.')
        {
            while ((c = read()) >= '0' && c <= '9')
            {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}



}

my code
whats the problem in this code . ??

For input
1
4 3
1 2
1 3
1 4

The answer according to the editorial is -
2 1 1 1

But isn’t it wrong because after the removal of vertex 1, we would have 4 separate vertices i.e. all independent graphs with single vertex ?

But the problem statement is ambiguous, regarding K sets of vertices and K subgraphs.

Oh damn those 1-indices :frowning:
Thanks a ton @denjell for taking the time out to read my code :smiley: