5
Tôi đang cố gắng tìm ra số lượng nút được bao phủ tối đa qua một đường dẫn trong một biểu đồ nhất định. Tôi đã thực hiện một chương trình bằng cách sử dụng đệ quy nhưng nó là đưa ra câu trả lời chỉ cho một số đồ thị đơn giản không phải trên đồ thị phức tạp.Làm cách nào để bao gồm số lượng nút tối đa qua đường dẫn nhất định trong biểu đồ?
Đầu vào được đưa ra trong một mảng chuỗi như 1 # 2: có nghĩa là nút 1 được kết nối với nút 2 hoặc ngược lại.
Tôi đã tạo một ma trận có tổng kích thước nút và nếu nút được kết nối được đặt 1 khác -1 trong ma trận. Ma trận này được sử dụng để tính toán nút được bao phủ tối đa trong đường dẫn.
Code:
import java.io.*;
import java.util.*;
public class Medium
{
public static int node_covered;
public static int big=0;
public static boolean[] visited;
public static int matrix_length;
public static String[][] matrix;
public static String[] input=new String[]
//answer is 7.
{"1#2", "2#3","3#4","3#5","5#6","5#7","6#7","7#8"};
public static void main(String[] args){
int total_nodes=maxno_city(input);
System.out.println(total_nodes);
}
public static int maxno_city(String[] input1)
{
int ln=input1.length;
HashSet hs = new HashSet();
for(int i=0; i<ln;i++)
{
String[] temp=input1[i].split("#");
hs.add(temp[0]);
hs.add(temp[1]);
}
matrix_length=hs.size();
hs.clear();
matrix=new String[matrix_length][matrix_length];
//initialize matrix
for (String[] row : matrix)
Arrays.fill(row, "-1");
//System.out.println(Arrays.deepToString(matrix));
for(int i=0;i<matrix_length;i++)
{
for(int j=0; j<matrix_length;j++)
{
String[] temp=input1[i].split("#");
int first=Integer.parseInt(temp[0])-1;
int second=Integer.parseInt(temp[1])-1;
matrix[first][second]="1";
matrix[second][first]="1";
}
}
//System.out.println(Arrays.deepToString(matrix));
//initialized
//now start work on matrix
for(int i=0;i<matrix_length;i++)
{
for(int j=0; j<matrix_length;j++)
{
visited=new boolean[matrix_length];
if(matrix[i][j].equals("1"))
{
node_covered=0;
getNextPath(j,i);
//visited[i]=true;
}
}
}
return big;
}
//recursive method
public static void getNextPath(int path,int visited_node)
{
boolean flag=false;
visited[visited_node]=true;
node_covered++;
for(int i=0;i<matrix_length;i++)
{
if(matrix[path][i].equals("1") && visited[i]==false)
{
//visited[i]=true;
flag=true;
getNextPath(i,path);
//visited[i]=false;
}
}
if(flag==false)
{
if(big<node_covered)
{
big=node_covered;
//System.out.println(big);
}
}
else
{
node_covered--;
}
//visited[path]=false;
}
}
Nơi tôi đang làm sai lầm trong mã trên?
điều này có thể được hoàn tất, không chắc chắn phải kiểm tra –
Nó có giải pháp ... Tôi đang bỏ qua điều gì đó. Đó là lý do tôi hỏi ở đây. –
Sẽ tốt hơn nếu bạn chỉ ra nguồn sự cố để chúng tôi cũng có một số trường hợp thử nghiệm. –