풀이 방법 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..