# Algorithm for solving FIRESC

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

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

``````/*
* 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;
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)
{
}

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();

{
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;
}

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…

btw…+1 for first trying and then asking…

2 Likes

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

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

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

//