/************************************************ * Count number of trees in a forest * --------------------------------- * 1. Apply DFS on every node. * 2. Increment count by one * 3. Again perform DFS traversal if some nodes yet not visited. * 4. Count will give the number of trees in forest. * ---------------------------------------------- * let, vertex = 5, edge = 3 (0 - 1, 0 - 2, 3 - 4) * tree will be (1 - 0 - 2), (3 - 4), so total 2. *************************************************/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define mem(x,y) memset(x,y,sizeof(x)) #define CLEAR(x) memset(x,0,sizeof(x)) #define pb push_back #define Sort(v) sort(v.begin(),v.end()) #define _sort(s, n) sort(s, s+n) #define sqr(x) ((x)*(x)) #define le 50001 #define ERR 1e-9 #define pi (2*acos(0)) #define PI 3.141592653589793 #define MX 1e9 #define scanint(a) scanf("%d", &a) #define scanLLD(a) scanf("%lld", &a) typedef long long ll; using namespace std; /* -------------------------- */ void DFS_again(int u, vector adj[], vector &visited) { visited[u] = true; for (int v = 0; v < adj[u].size(); v++) if (!visited[adj[u][v]]) DFS_again(adj[u][v], adj, visited); } int count_TREE(vector adj[], int nVertex) { vector visited(nVertex, false); int cnt = 0; for (int u = 0; u < nVertex; u++) { // DFS if (!visited[u]) { DFS_again(u, adj, visited); cnt++; } } return cnt; } int main() { int nVertex, nEdge, u, v; scanf("%d %d", &nVertex, &nEdge); vector adj[nVertex]; for (int i = 0; i < nEdge; i++) { scanf("%d %d", &u, &v); adj[u].pb(v); adj[v].pb(u); } cout << count_TREE(adj, nVertex) << "\n"; return 0; } /******************************* INPUT ---- - first line, n = 5 Vertex, m = 3 Edge 5 3 0 1 0 2 3 4 OUTPUT ----- 2 ******************************/