/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int e = sc.nextInt();
Graph g = new Graph(n);
for(int i = 0; i < n;i++){
g.addNode(i);
}
for(int i = 0; i < e; i++){
int a = sc.nextInt();
int b = sc.nextInt();
g.addEdge(a-1 , b-1);
}
g.dft();
// System.out.println(n-e);
}
}
}
class Node{
int data;
boolean visited;
Node(int data){
this.data = data;
visited = false;
}
}
class Graph{
private Node[] nodeList;
private int[][] adjMatrix;
private int numberNode;
private int cc_size;
//private QueueClass queue;
Graph(int size){
int MAX_Nodes = size;
nodeList = new Node[MAX_Nodes];
adjMatrix = new int[MAX_Nodes][MAX_Nodes];
numberNode = 0;
//Queue<int> queue = new LinkedList<>();
}
void addNode(int element){
nodeList[numberNode++] = new Node(element);
}
void addEdge(int start, int end){
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
private int getAdjUnvisitedNode(int node){
for(int j = 0; j < numberNode; j++){
if(adjMatrix[node][j] == 1 && nodeList[j].visited == false ){
return j;
}
}
return -1;
}
void dfs(int i){
nodeList[i].visited = true;
cc_size += 1;
int Node1;
while((Node1 = getAdjUnvisitedNode(i)) != -1){
dfs(Node1);
}
}
void dft(){
int count = 0;
long Route_leader = 1;
for(int i = 0; i < numberNode; i++){
if(!nodeList[i].visited){
count += 1;
cc_size = 0;
dfs(i);
Route_leader = (Route_leader*cc_size)%1000000007;
}
}
//System.out.println(numberNode);
System.out.println(count+" "+Route_leader);
}
}
Please format your code by adding ``` before and after the code OR share a link to the submission.
1 Like
adjMatrix = new int[MAX_Nodes][MAX_Nodes];
Max_Nodes can be as big as 10^5.
2 Likes
ok i will use adjacency list instead of adjacency matrix.
1 Like