Fire Escape Routes Codechef Solution|Problem Code: FIRESC

Fire Escape Routes Codechef Solution

Problem

There are NN people working in a building, and each one works in a separate cabin. Chef’s employees are numbered by integers from 11 to NN, inclusive. Chef wants to ensure the safety of his employees. He wants to have fire escapes in the building and wants to train the employees to use these by conducting mock drills.

Chef knows that the number of people working in his office can be very large. In order to avoid crowding of a common fire escape route during emergency, Chef has decided to build multiple fire escapes. For the safety of every employee, each cabin has a fire exit which is connected to one of the fire escape routes.

A lot of employees are friends with each other. The friendship is mutual. This means that if employee ii is a friend of employee jj then employee jj is a friend of employee ii as well. But friendship is NOT necessarily transitive. This means that if employee ii is a friend of employee jj AND employee jj is a friend of employee kk, then employee ii and employee kk need not necessarily be friends.

If two employees are friends, they do not want to escape through different routes. This complicates the task for the Chef. As already mentioned, he wants to have the maximum number of fire escape routes to ensure maximum safety. Also, for every escape route, one of the employees using that route needs to be appointed as the fire drill captain. The captain will be responsible for conducting the mock drills and train all the employees using that route. Your task is simple. Given the number of employees and the friendship list, you need to tell the Chef the maximum number of fire escape routes that he can have in the building and the number of ways of selecting the captains for every route. Since the number of ways can be really large, output this value modulo 109+7109+7.

Input

  • The first line of the input contains a single integer TT, denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains two space-separated integers NN and MM, denoting the number of employees and the number of friendship relations, respectively.
  • Each of the following MM lines contains two space-separated integers ii and jj, denoting that employee ii and employee jj are friends.

Output

For each test case, output a single line containing two space separated integers, denoting the maximum number of distinct fire escape routes that can be constructed and the number of ways of selecting the captains modulo 109+7109+7.

Constraints

  • 1≤T≤51≤T≤5
  • 1≤N≤1051≤N≤105
  • 0≤M≤1050≤M≤105
  • 1≤i,j≤N1≤i,j≤N
  • i≠ji≠j
  • For any pair of employees ii and jj such that 1≤i,j≤N1≤i,j≤N, at most one pair among (i,j)(i,j) and (j,i)(j,i) will appear in the input

Example Input

3
4 2
1 2
2 3
5 3
1 2
2 3
1 3
6 3
1 2
3 4
5 6

Example Output:

2 3
3 3
3 8

Fire Escape Routes – CodeChef Solution in CPP

#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050
#define ll long long
#define ld long double
#define lli long int
#define pb emplace_back
#define INF 1000000000
#define mod 1000000007
// trignometric function always give value in Radians only
#define PI acos(-1) //3.1415926535897932384626433832795028
#define dsin(degree) sin(degree*(PI/180.0))
#define dcos(degree) cos(degree*(PI/180.0))
#define dtan(degree) tan(degree*(PI/180.0))
#define rsin(radian) sin(radian)
#define rcos(radian) cos(radian)
#define rtan(radian) tan(radian)
#define loop(i,n) for (lli i = 0; i < n; i++)
#define loopitr(xt,vec) for (auto xt : vec)
#define FOR(i,a,b) for (lli i = a; i < b; i+=1)
#define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
#define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
#define itr :: iterator it
#define WL(t) while(t --)
#define all(v) v.begin(),v.end()
#define sz(x) int(x.size())
#define F first
#define S second
#define mii map<lli,lli>
#define vi vector<lli>
#define seti set<lli>
#define pii pair<lli,lli>
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)
template <typename T>
void print(T x){cout<<x<<endl;}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
#define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
#define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
#define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
#define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
#define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
#define FD(N) fixed<<setprecision(N)
#define endl '\n'
#define deb(x) cout<<#x<<" "<<x<<endl;
ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}
ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}
ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}
// chandan1,2
void chandan1(){int y=1;return;}
void chandan2(){
        loop(i,10){
        lli x=1;
    }
    return(chandan1());
}
lli fact[100001];
void facto(){
    fact[0] = 1;
    for(lli i=1;i<=100000;i++)
        fact[i]  = modmul(fact[i-1],i);
}
lli bfs(vi adj[],bool vis[], lli dist[], lli parent[] , lli s){
    queue<lli>q;
    q.push(s);
    vis[s]=1;
    dist[s]=0;
    parent[s] = s;
    lli cnt=0;
    while(q.empty()==false){
        lli x = q.front();
        q.pop();
        cnt++;
        for(auto xt : adj[x])
            {
                if(!vis[xt])
                {
                    dist[xt] = dist[x]+1;
                    vis[xt]=1;
                    q.push(xt);
                    parent[xt] = x;
                }
            }
    }
    return cnt;
}
int main(){
fastio
lli t=1;
cin>>t;
chandan2();
while(t--) {
    lli v,e,source,destin,n,q;
    cin>>v>>e;
    vi adj[v+1];
    loop(i,e){
        lli x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    bool vis[v+1]={0};
    lli dist[v+1]={0};
    lli parent[v+1]={0};
    lli cc_cnt=0;
    lli res = 1;
    for(lli i=1;i<=v;i++){
        if(!vis[i]){
            lli ways = bfs(adj,vis,dist,parent,i);
            cc_cnt++;
            res = modmul(res , ways);
        }
    }
    print2(cc_cnt,res);
  }
return 0;
}

Disclaimer: The above Problem (Fire Escape Routes) is generated by CodeChef but the solution is provided by Codeworld19.This tutorial is only for Educational and Learning purpose.

Leave a Comment