Advertisement
Guest User

Untitled

a guest
Mar 18th, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.29 KB | None | 0 0
  1. import java.io.File;
  2. import java.io.IOException;
  3. import java.nio.charset.Charset;
  4. import java.nio.file.Files;
  5. import java.nio.file.Paths;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.List;
  9. import java.util.Scanner;
  10.  
  11. public class BridgeNum {
  12. public static void main(String[] args) throws IOException {
  13. // Scanner in = new Scanner(System.in);
  14. List<String> lines = Files.readAllLines(Paths.get("11.txt"), Charset.defaultCharset());
  15. int n = Integer.parseInt(lines.get(0));
  16. int m = Integer.parseInt(lines.get(1));
  17. ArrayList<ArrayList<Integer>> ribs = new ArrayList<>();
  18. int[] count = new int[1];
  19. int[][] len = new int[n][2];
  20. int[] helper = new int[n];
  21. Arrays.fill(helper, -1);
  22. Arrays.fill(count, 0);
  23. for (int i = 0; i < n; i++){
  24. ArrayList<Integer> arr= new ArrayList<>();
  25. ribs.add(arr);
  26. }
  27. for (int i = 0;i < m;i++){
  28. String s = lines.get(i + 2);
  29. String str = "";
  30. int j = 0;
  31. while (s.charAt(j) != ' ') {
  32. str += s.charAt(j);
  33. j++;
  34. }
  35. int u = Integer.parseInt(str);
  36. j = 0;
  37. str = "";
  38. while (s.charAt(j) != ' ') {
  39. str += s.charAt(j);
  40. j++;
  41. }
  42. int v = Integer.parseInt(str);
  43. ribs.get(v).add(u);
  44. ribs.get(u).add(v);
  45. }
  46. for (int i = 0; i < n; i++){
  47. if (helper[i] == -1) dfs(i, -1, 0, count, helper, ribs, n, len);
  48. }
  49. System.out.println(count[0]);
  50. }
  51.  
  52. public static void dfs(int i, int e, int k, int[] count, int[] helper, ArrayList<ArrayList<Integer>> ribs, int n, int[][] len){
  53. helper[i] = 0;
  54. len[i][0] = len[i][1] = k++;
  55. int j = -1;
  56. while (++j < ribs.get(i).size()){
  57. int v = ribs.get(i).get(j);
  58. if (v == e) continue;
  59. if(helper[v] != -1) len[i][1] = Math.min(len[i][1], len[v][0]);
  60. else {
  61. dfs(v, i, k, count, helper, ribs, n, len);
  62. len[i][1] = Math.min(len[i][1], len[v][1]);
  63. if(len[v][1] > len[i][0]) ++count[0];
  64. }
  65. }
  66. }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement