그래프6 그래프 크기 구하기 int sz[MAX]; //따로 초기화 해둘 필요 없음 bool vst[MAX]; void dfs(int curr) { vst[curr] = true; sz[curr] = 1; for (int next : adj[curr]) { if (!vst[next]) { dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화 sz[curr] += sz[next]; } } } * 메인함수에서 dfs(rootNode)로 수행해야 모든 정점에 대해 구할 수 있음 * 양방향/단방향(부모->자식) 간선을 사용한 트리 모두에 대해 사용 가능 bool vst[MAX]; int dfs(int curr){ vst[curr]=true; int ccnt=1; for(int next: adj[curr]){ .. 2020. 1. 7. codeforces #597 div2 D - Shichikuji and Power Grid ( MST ) https://codeforces.com/contest/1245/problem/D 도시(최대 2000)마다 좌표, 파워설치비용, 간선연결가중치가 주어진다. 0번도시를 dummy vertex로 두고, 이 도시랑 연결하는 비용을 파워 설치 비용으로 둔 후, 모든 간선을 정렬하여 mst를 수행한다. mst를 뽑을 때 한 쪽 정점이 0번도시라면 그 도시는 파워를 설치한 도시이고, 양쪽 다 0번이 아니라면 두 도시는 연결된 도시이다. #include #include #include #include using namespace std; typedef pair P; typedef long long ll; const int MAX = 2001; struct Edge { int u, v; ll w; Edge(int u1.. 2019. 11. 4. 이전 1 2 다음