# pink_and_blue

SSkyFire

java

2 months ago

5.3 kB

0

Indexable

Never

^{}

Pink and Blue Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy. Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition: Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa. Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion. So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task. Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation. Input The first line is the number of test cases T. First line of each test case contains 2 space-separated integers - N and M - number of students and number of friendships present respectively. Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl. M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa. Output If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required. Else, print -1. Constraints 1 ≤ N ≤ 105 1 ≤ M ≤ 105 1 ≤ u, v ≤ N Colors of T-Shirt are represented by uppercase characters 'B' and 'G' Sample Input 3 3 2 B G B 1 2 1 3 6 9 B B B G G G 3 5 2 6 4 2 6 3 3 1 3 4 6 1 5 1 1 4 6 5 G G G B G G 6 3 1 3 2 3 4 3 5 3 Output 1 -1 2 Explanation #1 Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1. package blue_and_pink; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, friendship; static char []a; static int []color; static int [][]map; public static class Queue{ final int MAX_SIZE = 1000000; int []data = new int[MAX_SIZE]; int front; int rear; public Queue() { front = rear = -1; } public void init() { front = rear = -1; } public boolean isEmpty() { if(front == rear) return true; else return false; } public void enQueue(int element) { rear = rear + 1; data[rear] = element; } public int deQueue() { front = front + 1; return data[front]; } } static Queue queue; public static void resetColor() { for(int i=0; i<n; i++) { color[i] = 0; } } //1: xanh, 2 hong public static int bfs(int start, int mau) { queue.init(); resetColor(); queue.enQueue(start); color[start] = mau; boolean check = true; while (!queue.isEmpty()) { int p = queue.deQueue(); for(int i=0; i<friendship; i++) { if(map[i][0] == p) { if(color[map[i][1]] == 0) { color[map[i][1]] = 3 - color[p]; queue.enQueue(map[i][1]); } else if(color[map[i][1]] == color[p]) { check = false; } } else if(map[i][1] == p) { if(color[map[i][0]] == 0) { color[map[i][0]] = 3 - color[p]; queue.enQueue(map[i][0]); } else if(color[map[i][0]] == color[p]) { check = false; } } } if(check == false) { break; } } if(check == true) { int sumInversion = 0; for(int i=1; i<=n; i++) { if(a[i] == 'B' && color[i] != 1 || a[i] == 'G' && color[i] != 2) { sumInversion ++; } } return sumInversion; } else { return -1; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("src/blue_and_pink/input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner sc = new Scanner(System.in); int TC = sc.nextInt(); queue = new Queue(); for(int t=0; t<TC; t++) { n = sc.nextInt(); friendship = sc.nextInt(); a = new char[n+1]; color = new int[n+1]; map = new int[friendship][2]; for(int i=1; i<=n; i++) { a[i] = sc.next().charAt(0); } for(int i=0; i<friendship; i++) { map[i][0] = sc.nextInt(); map[i][1] = sc.nextInt(); } int minInversion = Integer.MAX_VALUE; for(int i=1; i<=n; i++) { for(int j=1; j<=2; j++) { int res = bfs(i, j); if(res != -1 && res < minInversion) { minInversion = res; } } } if(minInversion == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(minInversion); } } } }

Leave a Comment