# Untitled

ptrdung
c_cpp
15 days ago
2.0 kB
3
Indexable
Never
```#include <iostream>

using namespace std;

int N; // number of Students
int M; // number of friendships
int friendship[200002][3], visited[200002];
int gender[100002]; // 1: Boy, 2: Girl
int shirt[100002];  // 1: Blue, 2: Pink
int hasfriend[100000];

char temp;
int ans;
int total;
int temp1;

void DFS(int a, int s)
{
if(ans == -1) return;
total++;
shirt[a] = s;
if(shirt[a] != gender[a]) temp1++;

for(int i = 1; i <= 2 * M; i++)
{
if(friendship[i][0] == a && visited[i] == 0)
{
if(shirt[friendship[i][1]] != 0)
{
//cout << friendship[i][0] << " " <<  friendship[i][1];
ans = -1;
return;
}
else
{
visited[i] =1;
if(friendship[i-1][0] == friendship[i][1] && friendship[i-1][1] == friendship[i][0]) visited[i-1] = 1;
if(friendship[i+1][0] == friendship[i][1] && friendship[i+1][1] == friendship[i][0]) visited[i+1] = 1;
DFS(friendship[i][1], 3-s);
}
}
}
}

int main()
{
//freopen("input1.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
ans = 0;
cin >> N >> M;
for(int i = 1; i <= N; i++)
{
shirt[i] = 0;
hasfriend[i] = 0;
cin >> temp;
if(temp == 'B') gender[i] = 1;
else gender[i] = 2;
}
for(int i = 1; i <= M; i++)
{
cin >> friendship[2*i-1][0] >> friendship[2*i-1][1];
friendship[2*i][0] = friendship[2*i-1][1];
friendship[2*i][1] = friendship[2*i-1][0];
hasfriend[friendship[2*i-1][0]] = 1;
hasfriend[friendship[2*i-1][1]] = 1;
visited[2*i-1] =0;
visited[2*i]= 0;
}

for(int i = 1; i <= N; i++)
{
if(hasfriend[i] == 0) shirt[i] = gender[i];
}

for(int i = 1; i <= N; i++)
{
if(ans == -1) break;

if(shirt[i] == 0)
{
temp1 = 0;
total = 0;
DFS(i, 1);
if(ans == -1) break;
if(temp1 > total /2) ans = ans + total - temp1;
else ans = ans + temp1;

}
}
cout  << ans << endl;

}
return 0;
}```