Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.IOException;
- import java.nio.charset.Charset;
- import java.nio.file.Files;
- import java.nio.file.Paths;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.Scanner;
- public class BridgeNum {
- public static void main(String[] args) throws IOException {
- // Scanner in = new Scanner(System.in);
- List<String> lines = Files.readAllLines(Paths.get("11.txt"), Charset.defaultCharset());
- int n = Integer.parseInt(lines.get(0));
- int m = Integer.parseInt(lines.get(1));
- ArrayList<ArrayList<Integer>> ribs = new ArrayList<>();
- int[] count = new int[1];
- int[][] len = new int[n][2];
- int[] helper = new int[n];
- Arrays.fill(helper, -1);
- Arrays.fill(count, 0);
- for (int i = 0; i < n; i++){
- ArrayList<Integer> arr= new ArrayList<>();
- ribs.add(arr);
- }
- for (int i = 0;i < m;i++){
- String s = lines.get(i + 2);
- String str = "";
- int j = 0;
- while (s.charAt(j) != ' ') {
- str += s.charAt(j);
- j++;
- }
- int u = Integer.parseInt(str);
- j = 0;
- str = "";
- while (s.charAt(j) != ' ') {
- str += s.charAt(j);
- j++;
- }
- int v = Integer.parseInt(str);
- ribs.get(v).add(u);
- ribs.get(u).add(v);
- }
- for (int i = 0; i < n; i++){
- if (helper[i] == -1) dfs(i, -1, 0, count, helper, ribs, n, len);
- }
- System.out.println(count[0]);
- }
- public static void dfs(int i, int e, int k, int[] count, int[] helper, ArrayList<ArrayList<Integer>> ribs, int n, int[][] len){
- helper[i] = 0;
- len[i][0] = len[i][1] = k++;
- int j = -1;
- while (++j < ribs.get(i).size()){
- int v = ribs.get(i).get(j);
- if (v == e) continue;
- if(helper[v] != -1) len[i][1] = Math.min(len[i][1], len[v][0]);
- else {
- dfs(v, i, k, count, helper, ribs, n, len);
- len[i][1] = Math.min(len[i][1], len[v][1]);
- if(len[v][1] > len[i][0]) ++count[0];
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement