# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
17304 | 2015-11-19T11:44:00 Z | gs14004 | 지도 색칠하기 (GA3_map) | C++14 | 0 ms | 0 KB |
#include <algorithm> using namespace std; bool adj[20][20]; int col[20]; int bits, n; bool bad; void dfs(int x, int p){ if(col[x] && col[x] != p){ bad = 1; return; } else if(col[x]) return; col[x] = p; for(int i=0; i<n; i++){ if(!col[i] && adj[x][i] && (bits >> i) % 2 == (bits >> x) % 2){ dfs(i); } } } long long NumberOfMaps (int N, int M, int *A, int *B){ n = N; for(int i=0; i<M; i++){ adj[A[i]][B[i]] = 1; adj[B[i]][A[i]] = 1; } long long sum = 0; for(int i=0; i<(1<<(N-1)); i++){ bits = i; bad = 0; int cnt = 0; for(int i=1; i<=N; i++){ if(col[i]) continue; dfs(i); if(bad) break; cnt++; } if(bad) continue; sum += (2 << cnt); } return sum; }