ECAUG206 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Sunita Sen
Tester: Arnab Chanda
Editorialist: Sunita Sen

DIFFICULTY:

EASY-MED

PREREQUISITES:

DFS

PROBLEM:

Given an array of number of shops and roads connecting them, find the number of markets.

EXPLANATION:

We can simply run DFS on one shop and visit all the shops that can be reached. This gives us one market. Then for every unvisited shop, visit all reachable unvisited shops and so on.
The answer will be the number of times we needed to visit a new market.

SOLUTIONS:

Cpp Solution 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second

void dfs(vector<vector<int>> &adj, vector<int> &visited, int  k){
    for(auto i: adj[k]){
        if(!visited[i]){
            visited[i] = 1;
            dfs(adj, visited, i);
        }
    }
}


signed main(){
    int t = 1;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        vector<vector<int>> adj(n+1);
        rep(i,m) {
            int a,b;
            cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        vector<int> visited(n+1,0);
        int ans = 0;
        for(int i = 0; i <n ; ++i) {
            if(!visited[i]) {
                
                dfs(adj, visited, i);
                ans++;
            }
        }
        cout<<ans<<endl;
        
    }
}
3 Likes