FIRESC

Problem Link

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

int nodesInComponents;

const long MOD = 1e9 + 7;

bool visited[100001];;

void dfs(int s, vector<int> graph[])

{

visited[s] = true;

nodesInComponents++;

for(int v = 0; v < graph[s].size(); v++)

{

if(!visited[graph[s][v]])

{

dfs(graph[s][v], graph);

}

}

}

int main()

{

int t, n, m, i, j, noOfComponents;

long numWays;

cin >> t;

while(t--)

{

noOfComponents = 0;

numWays = 1;

cin >> n >> m;

vector<int> graph[n + 1];

for(int k = 0; k < n + 1; k++)

{

visited[k] = false;

}

for(int k = 0; k < m; k++)

{

cin >> i >> j;

graph[i].push_back(j);

graph[j].push_back(i);

}

for(i = 1; i <= n; i++)

{

if(!visited[i])

{

noOfComponents++;

nodesInComponents = 0;

dfs(i, graph);

numWays *= nodesInComponents;

numWays %= MOD;

}

}

cout << noOfComponents << " " << numWays << endl;

}

return 0;

}