# Pink and Blue 100/100

Ann

c_cpp

a year ago

4.2 kB

14

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. #include<iostream> using namespace std; #define M 100000 int qux[1000000], quy[1000000]; int n, m, f, r; int **a, visit[100005]; int temp[100005][2]; int gt[100005], mau[100005]; int number[100005], dem[100005]; int ketqua; void Init() { f = r = 0; for(int i = 1; i <= n; i++) visit[i] = 0; } int BFS() { Init(); qux[r] = 1; //quy[r] = 1; r++; visit[1] = 1; int temp; while(f != r) { temp = qux[f]; f++; for(int i = 1; i<= number[temp]; i++) { int next = a[temp][i]; if( visit[next] == 0) { visit[next] = 1; mau[next] = 1 - mau[temp]; if(mau[next] != gt[next]){ ketqua++; } qux[r++] = next; }else{ if(mau[next] == mau[temp]){ return -1; } } } } return ketqua; } int main() { int T; //freopen("input.txt","r", stdin); //freopen("output.txt","w", stdout); cin>>T; for(int tc=1;tc<=T;tc++){ ketqua = 0; cin >>n >> m; for(int i = 1; i <= n; i++){ number[i] = 0; mau[i] = -1; } char buff; for(int i= 1; i <= n; i++){ cin >> buff; if(buff == 'B'){ gt[i] = 1; }else{ gt[i] = 0; } } int x, y; a = new int*[n+1]; for(int i = 0; i < m; i++) { cin >> x >> y; //cout<<x<<":"<<y<<endl; number[x]++; number[y]++; temp[i][0] = x; temp[i][1] = y; } for(int i=1;i<=n;i++){ a[i] = new int[number[i]]; dem[i] = 0; } for(int i = 0; i < m; i++) { x = temp[i][0]; y = temp[i][1]; dem[x]++; dem[y]++; a[x][dem[x]] = y; a[y][dem[y]] = x; } //BFS/// mau[1] = gt[1]; int result1 = BFS(); int result2 = n - result1; if(result1>result2){ cout<<result2<<endl; }else{ cout<<result1<<endl; } } }