atcoder

# # Problem

## # Input

$N M$
$u_1 v_1$
$u_2 v_2$
...
$u_M v_M$

• $N$ - The number of vertices
• $M$ - The number of undirected edges
• $u_i v_i$ - Edge which connects $u_i$ and $v_i$

## # Output

Report the number of trees.

A tree is either

1. A connected graph which has only 1 vertex.
1. A connected graph which doesn't have a cycle.

# # Explanation

For each vertex, visit it if you haven't visited it yet.
If the vertex doen't have any edge, it's a tree.
If it has edges, visit its neighbor vertices.
If a visited vertex is found, it's a cycle, not a tree.
If any visited vertex is not found to the end, it's a tree.

You visit a vertex just once, so the time complexity is $O(N)$.

# # Time complexity

$O(N)$

# # Solution

#define MAX_N 100

Int N, M;
vector<Int> G[MAX_N];
vector<Int> done(MAX_N, false);

void input() {
Int u,v;
cin >> N >> M;

while (cin >> u >> v) {
u--,v--;
G[u].push_back(v);
G[v].push_back(u);
}
done.resize(N);
}

bool dfs_isTree(Int u, Int depth, Int parent) {
done[u] = true;
if (len(G[u]) == 0) return true;

bool cycle = false;
for (auto v: G[u]) {
if (v == parent) continue;
if (done[v]) return false;
cycle |= !dfs_isTree(v, depth + 1, u);
}
return !cycle;
}

void solve() {
Int counter = 0;
loop(u,0,N) {
if (done[u]) continue;
counter += dfs_isTree(u, 0, -1);
}
cout << counter << endl;
}

int main(void) {
input();
solve();
return 0;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!