For each unvisited cell, do the DFS (or BFS) traversal and keep the track of count

ll n,m;
char arr[1011][1011];
bool vis[1011][1011];

void dfs(ll i, ll j)
{
    //Check Base Conditions
    if ((i < 0) || (j < 0) || (i >= n) || (j >= m) || vis[i][j]==true || arr[i][j]=='#'){
        return;
    }
    //Mark the visited cell as True
    vis[i][j] = true;
    //Try to explore in all 4 possible directions
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
}
void solve()
{   
    ll ans = 0;
    cin>>n>>m;
    rep(i,0,n){
        rep(j,0,m){
            cin>>arr[i][j];
        }
    }
    //Initially mark all cells as unvisited
    memset(vis,false,sizeof(vis));
    for (ll i = 0; i < n; ++i){
        for (ll j = 0; j < m; ++j){
            if (!vis[i][j] && arr[i][j]=='.') //If current cell is unvisited and belongs to '.'(floor){
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Do the traversal from A to B and simultaneously store the directions in the array

For the traversal, you have to use BFS only. Why ?

ll n,m;
char arr[1011][1011];
bool vis[1011][1011];
ll prev_step[1011][1011];
ll dx[4]={-1,0,1,0};
ll dy[4]={0,1,0,-1};
string directions="URDL";


void solve()
{   
    cin>>n>>m;

    //Mark all unvisited cells as false
    memset(vis,false,sizeof(vis));


    queue<pair<ll,ll>> q;
    pair<ll,ll> begin;
    pair<ll,ll> end;

    rep(i,0,n){
        rep(j,0,m){
            cin>>arr[i][j];
            //Store the index of starting node and ending node
            if(arr[i][j]=='A'){
                begin=make_pair(i,j);
            }
            else if(arr[i][j]=='B'){
                end=make_pair(i,j);
            }
            
        }
    }



    q.push(begin);
    vis[begin.first][begin.second]=true;

    while(!q.empty()){
        pair<ll,ll> temp=q.front();
        q.pop();
        for(ll i=0;i<4;i++){
            pair<ll,ll> ok = make_pair(temp.first+dx[i],temp.second+dy[i]);

            //Base Cases
            if (ok.first<0 || ok.first>=n || ok.second<0 || ok.second>=m){
                continue;
            }
            if (arr[ok.first][ok.second]=='#'){
                continue;
            }
            if (vis[ok.first][ok.second]){
                continue;
            }


            //Mark the current cell as visited and store the directions
            vis[ok.first][ok.second] = true;
            prev_step[ok.first][ok.second] = i;
            q.push(ok);
        }
    }


    //If the ending node is visited, then there is exists a path between starting node and ending node
    if (vis[end.first][end.second])
    {
        cout<<"YES"<<"\n";
        vector<ll>steps;

        while(end != begin){
            ll ok1 = prev_step[end.first][end.second];
            steps.push_back(ok1);
            end=make_pair(end.first-dx[ok1], end.second-dy[ok1]);
        }

        reverse(steps.begin(), steps.end());

        cout<<steps.size()<<"\n";

        for(auto it:steps){
            cout<<directions[it];
        }
        cout<<endl;
        
    }
    //If ending node is not visited, there does not exist any path 
    else
    {
        cout<<"NO"<<"\n";
        return;
    }
}

If there are k connected components, then minimum number of roads required is (k-1)

Do DFS traversal on all unvisited nodes and store one node from each connected component

ll n,m;
vector<ll> adj[200001];
vector<bool>vis(200001);
vector<ll>paths;

void dfs(int node)
{
    vis[node]=true;
    for(auto it:adj[node]){
        if(!vis[it]){
            dfs(it);
        }
    }
}

void solve()
{   
    cin>>n>>m;
    while(m--){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
     
    fill(vis.begin(),vis.end(),false);
    
    for (ll i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            //Saving one node from each connected component
            paths.push_back(i);
            dfs(i);
        }
    }

    cout<<paths.size()-1<<endl;
    
    for(ll i=1;i<paths.size();i++){
        cout<<paths[i]<<" "<<paths[i]-1<<endl;;
    }

}

This is same as second problem

You can't do DFS traversal. Think why ?

• Do the BFS traversal from start node
• If target node is found in the path, stop there and store all the nodes from target node to start that occurred in the path

void bfs(vector<ll>adj[], int start, int end)
{
    vector<ll> ans; //To store the path
    bool vis[end+20];
    vector<ll> temp(end+20);
    temp[start]=-1;     
    memset(vis,false,sizeof(vis)); 

    vis[start] = true;

    queue<ll>q;
    q.push(start);

    while(!q.empty()){
        ll ok = q.front();
        for(auto it:adj[ok]){
            if(!vis[it]){
                vis[it]=true;
                temp[it]=ok;
                q.push(it);
            }
        }
        q.pop();
    }
    if (vis[end]){ //If end node is visited, it means there exist a path
        for(ll i=end; i!=-1; i=temp[i]){
            ans.push_back(i+1);
        }
    }

    reverse(ans.begin(),ans.end());

    if (ans.empty())
    {
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }

    cout<<ans.size()<<endl;
    for(auto it:ans){
        cout<<it<<" ";
    } 
}

void solve()
{   
    ll n,m;
    cin>>n>>m;
    vector<ll> adj[n+1];
    while(m--){
         ll a,b;
         cin>>a>>b;
         a--;b--;
         adj[a].push_back(b);
         adj[b].push_back(a);
    }
    //Do the BFS traversal from start node to end node
    bfs(adj,0,n-1);
}

We can use a graph coloring algorithm

The idea is to assign a color to each pupil in such a way that no two consecutive friends are assigned the same color.

ll n,m;
vector<vector<ll>>adj ;
vector<bool>vis;
vector<ll>ok(100001); //To store the colors

bool dfs(ll curNode, ll color)
{
    //Mark the current node as visited and assign the color
    vis[curNode] = true;
    ok[curNode] = color;

    for(auto it:adj[curNode]){
        if (!vis[it])
        {
            bool temp = dfs(it,color^1); //XOR the current color with 1 to change it from adjacent node's color
            if (temp==false)
            {
                return false;
            }
            else
            {
                if (ok[curNode] == ok[it])
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void solve()
{
    cin>>n>>m;

    adj.assign(n+1,{});
    vis.assign(n+1,false);

    while(m--){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    bool check = true;

    for (ll i = 1; i <= n; ++i){
        if (!vis[i]) //If the given node is unvisited, perform dfs travesal
        {
            check = dfs(i,0);
            if (!check){
                break;
            }
        }
    }

    if (!check){
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }

    //Print the color given to each pupil
    for (int i = 1; i <= n; ++i){
        cout<<ok[i]+1<<" ";
    }
    cout<<endl;
    
}

Just try to find the cycle in the graph. That's it. That's is the solution !

ll n,m;
ll start,en;
vector<vector<ll>>adj;
vector<bool>vis;
vector<ll>parent;


bool dfs(ll curNode, ll curParent)
{
    vis[curNode] = true;
    parent[curNode] = curParent;

    for(auto it:adj[curNode]){
        if(it==curParent){
            continue;
        }
        if(vis[it]){
            start = it;
            en = curNode;
            return true;
        }
        if (!vis[it]){
            if (dfs(it,curNode)){
                return true;
            }
        }
    }
    return false;
}

bool visit_all()
{
    for (ll i = 1; i <= n; ++i){
        if (!vis[i]){
            if (dfs(i,-1)){
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    cin>>n>>m;

    adj.assign(n+1,{});
    vis.assign(n+1,false);
    parent.resize(n+1);

    rep(i,0,m){
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if (!visit_all())   
    {
        cout<<"IMPOSSIBLE"<<"\n";
        return;
    }
    ll ok = en;
    vector<ll> cycle;
    cycle.push_back(en);
    while(ok != start){
        cycle.push_back(parent[ok]);
        ok = parent[ok];
    }
    cycle.push_back(en);
    cout<<cycle.size()<<"\n";
    for(auto it:cycle){
        cout<<it<<" ";
    }
    cout<<endl;

}