Untitled
plain_text
a month ago
2.4 kB
1
Indexable
Never
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m; static int[][] a = new int[305][305]; static int[][] b = new int[305][305]; static int[] parent = new int[305]; static int[] visited = new int[305]; static int res; public static void main(String[] args) throws FileNotFoundException { //Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(new File("C:\\Users\\SVMC\\workspace\\adv\\Test\\src\\input.txt")); int T = sc.nextInt(); for(int t=1; t<=T; t++){ n = sc.nextInt(); for(int i=0; i<n; i++){ parent[i]=-1; for(int j=0; j<n; j++){ b[i][j]=0; a[i][j]=sc.nextInt(); } } for(int i=0; i<n; i++){ visited[i]=0; } int vung = 0, cl=0; for(int i=0; i<n; i++){ if(visited[i]==0){ int tmp=BFS(i); vung++; if(tmp==1){ cl++; } } } for(int i=0; i<n; i++){ visited[i]=0; } for(int i=0; i<n; i++){ if(visited[i]==0){ DFS(i); } } int cau=0; if(vung!=cl){ for(int i=0; i<n-1; i++){ for(int j=i+1; j<n; j++){ if(a[i][j]==1 && b[i][j]!=1){ for(int z=0; z<n; z++){ visited[z]=0; } a[i][j]=0; a[j][i]=0; int tmp = 0; for(int z=0; z<n; z++){ if(visited[z]==0){ BFS(z); tmp++; } } a[i][j]=1; a[j][i]=1; if(tmp>vung) cau++; } } } } System.out.println(vung+" "+cl+" "+cau); } } static void DFS(int k){ visited[k]=1; for(int i=0; i<n; i++){ if(a[k][i]==1 && visited[i]==0){ parent[i]=k; DFS(i); }else if(a[k][i]==1 && visited[i]==1 && i!=parent[k]){ b[k][i] = 1; b[i][k] = 1; int tmp=k; while(tmp!=i){ b[tmp][parent[tmp]]=1; b[parent[tmp]][tmp]=1; tmp=parent[tmp]; } } } visited[k]=2; } static int BFS(int k){ int cnt=0; int[] q = new int[305*305]; int l=0, r=0; q[r++]=k; visited[k]=1; while(l<r){ k = q[l++]; cnt++; for(int i=0; i<n; i++){ if(a[k][i]==1 && visited[i]==0){ visited[i]=1; q[r++] = i; } } } return cnt; } }