pinkandbluequoc
quoc14
c_cpp
18 days ago
1.7 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, dem; int ok; int minn(int a, int b) { if (a < b) return a; return b; } 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; ok = 1; } } if (visit[i] == 0 && a[x][i] == 1) { if (check[x] == 1) { check[i] = 2; if (gender[i] == 'B') { dem++; } } else { check[i] = 1; if (gender[i] == 'G') { dem++; } } dfs(i); } } } void solve(int testcase) { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = 0; } } for (int i = 1; i <= n; i++) { cin >> gender[i]; } for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; a[u][v] = 1; a[v][u] = 1; } dem = 0; resetvisit(); check[1] = 1; ok = 0; if (gender[1] == 'G') { dem++; } dfs(1); if (ok == 0) { ans = dem; dem = 0; resetvisit(); check[1] = 2; if (gender[1] == 'B') { dem++; } dfs(1); if (ok == 0) { ans = minn(ans, dem); } else { ans = -1; } } else { ans = -1; } 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; }
Leave a Comment