# pinkandbluesol

quoc14
c_cpp
22 days ago
3.6 kB
3
Indexable
Never
caidat
```#include <iostream>
using namespace std;

int n, m;
char gender[100111];
int a[1000][1000];
// 1 xanh
// 2 do
// 0 chua phat
int check[100111];
int visit[100111];
int ans, lan1, lan2;
int ok;

void resetvisit() {
for (int i = 1; i <= n; i++) {
visit[i] = 0;
check[i] = 0;
}
}

void dfs(int x) {
if (ok == 1) return;
visit[x] = 1;

for (int i = 1; i <= n; i++) {
if (visit[i] == 1 && a[x][i] == 1) {
if (check[i] == check[x]) {
cout << x << " " << i << endl;
}
}
if (visit[i] == 0 && a[x][i] == 1) {

if (check[x] == 1) {
check[i] = 2;
}
else {
check[i] = 1;
}
dfs(i);
}
}
}

void solve(int testcase) {
cin >> n >> m;

for (int i = 1; i <= n; i++) {
cin >> gender[i];
}

int ok = 0;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
a[u][v] = 1;
a[v][u] = 1;
}
lan1 = 0;
check[1] = 1;
ok = 0;
resetvisit();
dfs(1);

if (ok == 1) {
cout << "quoc" << endl;
}
for (int i = 1; i <= n; i++) {
cout << check[i] << " ";
}
cout << endl;
cout << "#" << testcase << " " << ans << endl;
}

int main() {
freopen("Text.txt", "r", stdin);
int t; cin >> t;

for (int i = 1; i <= t; i++) {
solve(i);
}

return 0;
}

#include <iostream>

using namespace std;

const int oo = 99999999;

struct custom{
unsigned short int *arr;
int size;
};

custom mtk[100003];
int gender[100003];
int visit[3][100003];
short dem[100003];

int sizee(int node)
{
return mtk[node].size;
}

void pushh(int node, int v)
{
mtk[node].arr[++mtk[node].size] = v;
}

int pull(int node, int pos)
{
return mtk[node].arr[pos];
}

void reset_init(int n)
{
for (int i = 0; i<=n+1; i++)
{
mtk[i].size = 0;
delete[] mtk[i].arr;
mtk[i].arr = new unsigned short int[dem[i] + 2];
}
}

int n, m;
int kt[2];
int ans[2];

struct point
{
unsigned short int x;
unsigned short int y;
};

point tmpip[1000003];

void DFS(int index, int uu, int color)
{
visit[index][uu] = color;
if (gender[uu] != color) ans[index] += 1;
if (kt[index] == 1)  return;

int sizeuu = sizee(uu);
int newcolor = color*(-1);
for (int j  = 1; j<=sizeuu; j++)
{
int node = pull(uu, j);
if (visit[index][node] != 0)
{
if (visit[index][node] == color)
kt[index] = 1;
} else
DFS(index, node, newcolor);
}
}
int main()
{
//freopen("inpu.txt","r",stdin);
int ntc;
cin >> ntc;
for (int tc=1; tc<=ntc; tc++)
{
cin >> n >> m;
//cout << tc;
for (int i = 1; i <= n; i++)
{
dem[i] = 0;
visit[0][i] = 0;
visit[1][i] = 0;
char tm;
cin >> tm;
gender[i] = (tm == 'B'? 1 : -1);
}

for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
dem[u]++;
dem[v]++;
tmpip[i].x = u;
tmpip[i].y = v;
}
reset_init(n);

int max = 0;
for (int i = 1; i <= n; i++)
if (dem[i] > 0)
{
//cout << dem[i] << " ";
if (dem[i] > max) max = dem[i];
}

for (int i = 1; i <= m; i++)
{
pushh(tmpip[i].x, tmpip[i].y);
pushh(tmpip[i].y, tmpip[i].x);
}

kt[0] = 0; ans[0] = 0;
kt[1] = 0; ans[1] = 0;
// luot 0, nguoi 1, mac ao mau 1(xanh), doidadaonguoc = 0;
DFS(0, 1, 1);
DFS(1, 1, -1);

if (kt[0] == true && kt[1] == true)
{
cout << -1 <<endl;
} else if (kt[0] == false && kt[1] == false)
{
cout << (ans[0] < ans[1] ? ans[0] : ans[1]) << endl;
} else if (kt[1] == false)
cout << ans[0] << endl;
else cout << ans[1] << endl;

}
return 0;
}

```