Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define SZ(v) ((int)(v).size())
- #define pb push_back
- const int N = 2e5+9;
- const int inf = 1e9+9;
- vector<int> adj[N];
- bool vis[N];
- void DFS (int st_node) {
- vis[st_node] = true;
- for (int neg : adj[st_node]) {
- if (!vis[neg]) {
- DFS(neg);
- }
- }
- }
- /*
- 5 4
- 1 2
- 1 3
- 3 4
- 4 5
- 1 -> 2 3
- 2 -> 1
- 3 -> 1 4
- 4 -> 3 5
- 5 -> 4
- 6 ->
- */
- void run () {
- int n, m;
- cin >> n >> m;
- for (int i = 0; i < m; ++i) {
- int u, v;
- cin >> u >> v;
- // undirected
- // u -> v
- // v -> u
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- DFS(1);
- int count = 1;
- for (int node = 1; node <= n; ++node) {
- if (!vis[node]) {
- count++;
- DFS(node);
- }
- }
- cout << count << '\n';
- }
- int main () {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- freopen("/home/hamoudi/clion/hello.in", "rt", stdin);
- int tt;
- tt = 1;
- // cin >> tt;
- while (tt--)
- run();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement