Algorithm for solving FIRESC

general
1

I am trying to solve FIRESC.

My approach is as follows:
->Max number of fire escape routes = number of connected components in the graph.

->number of ways of selecting the captains = multiplication of size of each of the connected components.

My code is getting WA.

Is this the correct algorithm ?

In case anyone wants to see my code, here is the link:
Solution

1 Like
2

this is your corrected code…

/*
 * File:   main.cpp
 * Author: Prashant
 *
 * Created on 26 August, 2013, 2:29 PM
 */
#include<string.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MOD 1000000007

using namespace std;



class Graph
{
    long long int V;
    vector<long long int> *adj;
public:
    Graph(long long int v);
    void add_edge(long long int v, long long int w);
    long long int BFS(long long int start, bool *visited);
};

Graph::Graph(long long int v)
{
    V=v+1;
    adj = new vector<long long int>[V];
}

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

long long int Graph::BFS(long long int start, bool *visited)
{
    long long int captain=1;

    queue<long long int> Q;

    visited[start]=true;
    Q.push(start);

    vector<long long int>::iterator it;

    while(!Q.empty())
    {
        start=Q.front();
        Q.pop();

        for (it = adj[start].begin();  it!=adj[start].end(); ++it)
        {
            if(visited[*it]!=true)
            {
                visited[*it]=true;
                Q.push(*it);
                captain++;
            }
        }

    }

    return captain;


}

int main() {
    long long int t;
    cin>>t;
    while (t--) {
        long long int N,M;
        cin>>N>>M;

        Graph g(N);
        long long int v,w;
        for (long long int j = 0; j < M; j++) {
            cin>>v>>w;
            g.add_edge(v,w);
        }

        bool *visited = new bool[N+1];
        for(int z=0;z<=N;z++)     //error was here!!!
            visited[z]=false;
        long long int captain=1;
        long long int i=0;
        long long int count=0;
        for(i=1;i<=N;i++)
        {
            if(visited[i]!=true)
            {
                count=(count+1)%MOD;
                captain = (captain*(g.BFS(i, visited))%MOD)%MOD;
            }
        }
        cout<<count<<" "<<captain<<endl;
    }


    return 0;
}

the problem was in the fxn memset…to be specific…the way of using sizeof…it returns the size of that variable…in your case visited though being an array…was a mere pointer to that array…so the sizeof returned just 4…if u would have declared ur visited array as…

bool visited[N]

then the size of would have worked perfectly i.e., the way u wanted it to work…you can see this code to understand what im saying…LINK!!!
…hope this helps…:slight_smile:

btw…+1 for first trying and then asking…:slight_smile:

2 Likes
3

yes the algo is perfectly fine…maybe some minor mistake…:slight_smile:

4

closing this ques…as i see that u have got the green tick…:slight_smile:

5

Didn’t know this fact. I thanked you in my earlier comment but i see that it’s not here anymore :D. So, thanks again :slight_smile:

6

glad could help…just click on the green tick to indicate that the ans was accepted…:slight_smile: