Help in FIRESC

help
1

Problem: FIRESC
Code:

#include <bits/stdc++.h>

using namespace std;

const int size = 1e5+1;
const int mod = 1e9+7;
vector <int> adj[size];
int visited[size];
int ccsize;

void dfs(int node)
{
    visited[node] = 1;
    ccsize++;
    for (int child : adj[node])
        if (!visited[child])
            dfs(child);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, u, v;
        cin >> n >> m;
        for (int i = 0; i < m; ++i)
        {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        long long exits = 0, res = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (!visited[i])
            {
                ccsize = 0;
                dfs(i);
                ++exits;
                res = ((res * ccsize) % mod);
            }
        }
        cout << exits << " " << res % mod << '\n';
        memset(visited, 0, sizeof(visited));
        for (int i = 0; i < size; ++i) fill(adj[i].begin(), adj[i].end(), 0);
    }
}

My program works fine for maximum number of exits (connected components). However, for some reason the program doesn’t work for test cases > 1 (finding the number of ways the team leaders can be arranged). I tried to find out what was wrong. From the second testcase, the ccsize (connected component size) of the first connected component is increased by 1. Suppose that there is a graph with 3 connected components and their sizes are 2, 1, 1, the program will run it for 3, 1, 1. How do I fix this?

2

I think the main problem is your reset. You should do adj[i].clear();. My guess is you are visiting 0 also after the second test case, because fill makes the elements 0, and doesn’t delete the elements.

Also your code is really well indented and has good variable names, so it’s very easy to understand.

1 Like
3

changing fill(adj[i].begin(), adj[i].end(), 0) to adj[i].clear() worked. Thanks for your help and for the feedback.