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; }
Leave a Comment