What's wrong with my approach in FIRESC ?

general
,
1

There are recent questions about people asking for debugging, but I really need help in this.
I will comment on my approach wherever appropriate.

Please help!

#include <bits/stdc++.h>

using namespace std;

typedef long long lld;

#define MOD 1000000007
#define scin(a) scanf("%d",&(a))

long long cnt = 0; //Maintains cardinality of current graph
long long parts = 0; //Maintains number of components
long long ans = 1; //Maintains product of size of all graphs

class Graph { //Graph class from GFG
    int V;
    list<int> *adj; //Stores graph as adjacency list

    void DFSUtil(int v, bool visited[]);

public:
    explicit Graph(int V);

    void addEdge(int v, int w);

    void DFS(int v);

    void connectedComponents();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
    adj[w].push_back(v);
}


void Graph::DFSUtil(int v, bool visited[]) {
    visited[v] = true;
    cnt++; //Counts number of nodes in current graph
    for (int &i : adj[v])
        if (!visited[i])
            DFSUtil(i, visited);
}

void Graph::DFS(int v) {
    bool visited[V];
    DFSUtil(v, visited);
}

void Graph::connectedComponents() { //Counts number of connected components in the graph (Adapted from GFG again)!
    bool visited[V];
    for (int v = 0; v < V; v++)
        if (!visited[v]) {
            DFSUtil(v, visited);
            parts++; //Counts total number of parts (or unconnected roots)
            ans *= cnt; //Counts number of ways Chef can choose fire captains
            if (ans > MOD)
                ans %= MOD;
            cnt = 0; //Reset size of graph as root has changed
        }
}

int main() {
    int T;
    scin(T);
    while (T--) {
        int N, M;
        scin(N);
        scin(M);
        Graph fire(N);
        int i, j;
        for (int k = 0; k < M; k++) {
            scin(i);
            scin(j);
            fire.addEdge(--i, --j);
        }
        fire.connectedComponents();
        printf("%lld %lld\n", parts, ans);
        //Reset all counter variables.
        cnt = 0;
        parts = 0;
        ans = 1;
    }
    return 0;
}

This is the first time I am attempting graph-based problems. All help I can get is appreciated. Thanks in advance.

2

Could someone please help me out over here!

3

Two things that you missed:

  1. According to the question friendship is mutual. That is , if i is friend of j then j is also a friend of i. So you have to add edge (j , i) in the graph.
  2. Second thing that you missed is you have to initialize visited array to false when you are declaring it in Connected Component function. Memset can you be used for that purpose.

Suggestion : Always try to write code by your self. Try until you think that I would not be able to write the code. This is just a suggestion. What to do or not to do solely depends on you.

Solution Link : Solution Link

Hope this helps.

Cheers!

1 Like
4

Hey @sorcerer48, thanks for replying.

adj[v].push_back(w);
adj[w].push_back(v);

Doesn’t this satisfy the first point?

Also, isn’t a bool array initialized to false by default when declared?

Sorry, I sound noobish, because this is the only time I am trying to solve graph-based problems.

5

I guess I assumed the second point wrong! Got an AC! Thanks!

6

Yes my first point was kind of wrong because I didn’t see that you are adding both the type of edges in addEdge function.
And secondly boolean array is not initialized to false at the time of declaration. So I think this is the only mistake you made in this implementation.

1 Like