풀이 방법 spanning tree의 간선의 개수를 구하는 간단한 dfs 문제다. spanning tree의 간선의 개수는 dfs 또는 bfs 탐색 중 사용하는 간선을 모으면 된다. 코드 #include #include #include using namespace std; bool visited[1003]; vector v; int ans; void dfs(int s) { visited[s] = true; ans++; for (auto i : v[s]) { if (!visited[i]) dfs(i); } } int main() { int T; scanf("%d", &T); while (T--) { int N, M; scanf("%d %d", &N, &M); v.clear(); v.resize(N + 1)..

풀이 방법 유니온 파인드라는 자료구조를 이용하여 풀이하였다. 입력받은 두개의 루트 노드가 같으면 사이클이 형성되었다고 판단하고, 다르다면 두개의 트리를 합친다. 코드 #include #include using namespace std; int par[500005], level[500005]; int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void merge(int x, int y) { int a = find(x), b = find(y); if (a == b) return; if (level[a] > level[b]) swap(a, b); if (level[a] == level[b]) level[b]++; par[a..

풀이 방법 dp[i][j] : i번째 추까지 사용했을 때 무게 j를 만들 수 있는지 여부 i번째 상태는 i - 1번째 상태에 i번째 무게만큼 더할 것인지 뺄 것인지 아무것도 안 할 것인지로 정의할 수 있다. 코드 무게가 음수인 경우를 커버하기 위해 40000을 기본값으로 했다. #include int weight[32]; bool dp[32][80004]; int main() { int N; scanf("%d", &N); for (int i = 1; i