#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
vectorcomponents;
ll count1;
void add_edge(vector graph[], ll x, ll y){
graph[x].push_back(y);
graph[y].push_back(x);
}
ll dfs(vectoradj[], ll root, bool *visited){
visited[root] = true;
count1++;
vector neighbour = adj[root];
vector :: iterator ptr;
for(ptr = neighbour.begin(); ptr<neighbour.end(); ptr++)
if(!visited[*ptr])
dfs(adj,*ptr, visited);
return count1;
}
ll count(vector adj[], ll n){
bool visited[n];
ll count = 0,i;
for(i = 0; i<n; i++)
visited[i] = false;
for(i = 0; i<n; i++){
if(visited[i] == false){
count++;
count1 = 0;
components.push_back(dfs(adj,i,visited));
}
}
return count;
}
int main(){
int t;
cin>>t;
while(t–){
ll n,m,i;
cin>>n>>m;
vector <ll> graph[n];
while(m--){
ll x,y;
cin>>x>>y;
add_edge(graph,x-1,y-1);
}
ll mul = 1;
vector<ll>::iterator ptr;
cout<<count(graph,n)<<" ";
for(ptr = components.begin(); ptr<components.end(); ptr++)
mul = mul*(*ptr);
cout<<mul%mod<<endl;
components.clear();
for(i = 0; i<n; i++)
graph[i].clear();
}
}
I wrote this code for Fire Escape Routes Problem in easy section. It passed all the test cases but it is still wrong, i guess edge cases are unable to pass this code. So anyone pls help me out.
The concept that i used is I used DFS method to count the components of the graph and then i found the sub-components of the graph. And to get the number of captains i multiplied the number of sub-component of one connected graph to another