PinkAndBlue - NDDCoder

#include<iostream>

using namespace std;
int T,tc;
int n, m;
int gender[100001];
int initColor[100001];
int color[100001];
int edges[100000][2];
int adjVertex[100001];
int **adj;
int queue[100001];
int head, tail;
int vs[100001];
int minInservion;

int canAssignColor(int student, int c){
	for (int i=1;i<=adj[student][0];i++){
		if (color[adj[student][i]]==c) return false;
	}
	return true;
}

int solution(){
	for (int i=1;i<=n;i++) vs[i]=0;
	head=0;
	tail=0;
	queue[0]=1;
	vs[1]=1;
	color[1]=0;
	while (head<=tail){
		int tstudent=queue[head++];
		int tcolor=color[tstudent];
//		cout<<"top "<<tstudent<<" "<<tcolor<<endl;
		int newColor=1-tcolor;
		for (int i=1;i<=adj[tstudent][0];i++){
			int student = adj[tstudent][i];
//			cout<<"checking "<<student<<" "<<newColor<<endl;
			if (!vs[student] && canAssignColor(student, newColor)){
				tail++;
				queue[tail]=student;
//				cout<<"insert "<<student<<" "<<newColor<<endl;
				color[student]=newColor;
				vs[student]=1;
			}
		}
	}
//	cout<<"tail "<<tail<<endl;
	if (tail==n-1){
		int inversion1=0, inversion2=0;
		// calculate inversion
		for (int i=1;i<=n;i++){
//			cout<<initColor[i]<<" ";
			if (initColor[i]!=color[i]) inversion1++;
			else inversion2++;
		}
//		cout<<endl;
//		cout<<"inversions "<<inversion1<<" "<<inversion2<<endl;
		if (inversion1<inversion2) return inversion1;
		else return inversion2;
	}
	return -1;
}

int main(){
	freopen("PinkAndBlue.txt","r",stdin);
	cin>>T;
	for (tc=1;tc<=T;tc++){
		cin>>n>>m;
		adj=new int*[n+1];
		for (int i=1;i<=n;i++){
			adjVertex[i]=0;
			color[i]=-1;
			// read gender
			char c;
			cin>>c;
			if (c=='B') gender[i]=0;
			else if (c=='G') gender[i]=1;
//			cout<<gender[i]<<" ";
			// assign init color
			initColor[i]=gender[i];
		}
		// find number of memory to allocate
		for (int i=0;i<m;i++){
			cin>>edges[i][0]>>edges[i][1];
			adjVertex[edges[i][0]]++;
			adjVertex[edges[i][1]]++;
		}
		// allocate memory
		for (int i=1;i<=n;i++){
			adj[i]=new int[adjVertex[i]+1];
			adj[i][0]=0;
		}
		// assign adj list
		int tmp1, tmp2;
		for (int i=0;i<m;i++){
			tmp1=edges[i][0];
			tmp2=edges[i][1];
			
			adj[tmp1][0]++;
			int tmp3=adj[tmp1][0];
			adj[tmp1][tmp3]=tmp2;
			
			adj[tmp2][0]++;
			int tmp4=adj[tmp2][0];
			adj[tmp2][tmp4]=tmp1;
		}
		
//		for (int i=1;i<=n;i++){
//			cout<<i<<" ";
//			for (int j=1;j<=adj[i][0];j++){
//				cout<<adj[i][j]<<" ";
//			}
//			cout<<endl;
//		}
		
		// solution
//		cout<<"#"<<tc<<" ";
		cout<<solution()<<endl;
	}
}