ARC 037 B - バウムテスト
問題概要
連結成分の中で、閉路がなく、木である連結成分の個数を求める。
解法
閉路を検出する問題。dfsで探索して、すでに探索した頂点をmemoで記録しておいて、同じところに2度来たら、その連結成分は閉路を持つので木ではないのでカウントしない。
ミス
なし。
コード
#include <iostream> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int n, m; vector<int> G[110]; bool memo[110]; bool flag; void dfs(int c, int p){ for(auto next : G[c]){ if(next == p) continue; if(memo[next]){//閉路 flag = false; }else{ memo[next] = true; dfs(next, c); } } return; } int main(void){ cin >> n >> m; rep(i, m){ int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } rep(i, 110) memo[i] = false; int ans = 0; rep(i, n){ if(memo[i] == false){//まだ調べていない頂点 flag = true; dfs(i, -1); if(flag) ans++; } } printf("%d\n", ans); return 0; }