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.
9 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: CodeChef: Practical coding for everyone
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();
}
}
}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.
Just sharing my solution. It might be helpful for folks who code in JAVA.
Solution:- CodeChef: Practical coding for everyone
Hope this helps!
I’m getting TLE only for task#6 of subtask 1 . It would to helpful if the test cases are revealed after the contest.
According to editorial , if graph has odd no of edges we can remove one vertex with odd degree and put that in another group and just with k = 2 we have both groups having even edges but for image shared above if we put one of the vertex of cut set we will get 3 groups having 1,1,0 edges but our logic will give 2 groups as output so I think editorial is either wrong or it missed some boundary condition .
can you help me , how can i implement cut edge boundary condition .
Read again. The problem nowhere said that the graph has to be connected.
You get 1 group with 0 edges, and 1 group with 2 connected components having 3 and 1 edges respectively. Both of these are part of a single group.
3 Likes
yaa ,got it .Thanks for explaining.
1 Like
Same
(10 chars)
Thanks For explaining . I read Editorial again and it helped me . Finally got accepted 
1 Like
Sample test-case output doesn’t match testers. Please correct it.
Output of sample case as explained :-
2
1 2 1 1 2
Correct Solution/Testers solutions gives :-
2
1 2 1 1 1
I don’t think so, in the third case, removing two nodes with even number of edges don’t mean removeing odd numbers of edges, if there two edge between the two nodes, it is also remove even edges