Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, m;
- vector <int> edges[100010];
- bool visited[100010], f = false;
- void DFS(int vertix, int prev) {
- visited[vertix] = true;
- for (int i = 0; i < edges[vertix].size(); i++) {
- if (!visited[edges[vertix][i]]) {
- DFS(edges[vertix][i], vertix);
- } else if (edges[vertix][i] != prev) {
- f = true;
- }
- }
- }
- int main()
- {
- cin >> n >> m;
- for (int i = 0; i < m; i++) {
- int x, y;
- cin >> x >> y;
- x--, y--;
- edges[x].push_back(y), edges[y].push_back(x);
- }
- int res = 0;
- for (int i = 0; i < n; i++) {
- if (!visited[i]) {
- f = false;
- DFS(i, -1);
- if (!f)
- res++;
- }
- }
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement