結果
問題 | No.806 木を道に |
ユーザー |
|
提出日時 | 2019-03-22 22:04:13 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 994 bytes |
コンパイル時間 | 1,441 ms |
コンパイル使用メモリ | 160,104 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-09-19 05:24:24 |
合計ジャッジ時間 | 3,198 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> graph[100010]; int vi[100010] = {}; int dfs(int idx){ vi[idx] = 1; bool flag = false; int ans = 0; for(int i = 0;i < graph[idx].size();i++){ if(vi[graph[idx][i]] == 0){ flag = true; ans += dfs(graph[idx][i]); } } if(flag){ return ans; }else{ return 1; } } int main(){ int n; cin >> n; int a, b; for(int i = 0;i < n-1;i++){ cin >> a >> b; a--, b--; graph[a].push_back(b); graph[b].push_back(a); } int used[100010] = {}; int root = 0; bool flag; do{ flag = false; used[root] = 1; for(int i = 0;i < graph[root].size();i++){ if(used[graph[root][i]] == 0){ flag = true; root = graph[root][i]; break; } } }while(flag); cout << dfs(root)-1 << endl; return 0; }