Java实现冗余路径Redundant Paths

Description

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. 

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. 

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

Input

Line 1: Two space-separated integers: F and R 

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

Output

Line 1: A single integer that is the number of new paths that must be built.

Sample Input

7 7

1 2

2 3

3 4

2 5

4 5

5 6

5 7

Sample Output

2

Hint

Explanation of the sample: 

One visualization of the paths is:

   1   2   3

   +---+---+

       |   |

       |   |

 6 +---+---+ 4

      / 5

     /

    /

 7 +

Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.

   1   2   3

   +---+---+

   :   |   |

   :   |   |

 6 +---+---+ 4

      / 5  :

     /     :

    /      :

 7 + - - - -

Check some of the routes:

1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2

1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4

3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7

Every pair of fields is, in fact, connected by two routes. 

It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.

中文说明

为了从一个F（1<=F<=5000）放牧区（编号为1…F）到另一个放牧区，贝西和其他牛群被迫穿过腐烂的苹果树附近。奶牛现在已经厌倦了经常被强迫走一条特定的路，并且想要建造一些新的路，这样它们就可以在任何一对田地之间选择至少两条独立的路。它们目前在每对字段之间至少有一条路由，并且希望至少有两条。当然，他们只能在从一个领域到另一个领域的官方道路上旅行。

给出当前一组R（F-1<=R<=10000）路径的描述，每个路径正好连接两个不同的字段，确定必须构建的新路径（每个路径正好连接两个字段）的最小数目，以便在任何一对字段之间至少有两个单独的路径。如果路线不使用相同的路径，则认为它们是分开的，即使它们沿途访问相同的中间字段也是如此。

同一对字段之间可能已经有多条路径，您也可以构建一条新路径，将同一字段与其他路径连接起来。

输入

第1行：两个空格分隔的整数：f和r

行2…r+1：每行包含两个空格分隔的整数，这些整数是某些路径端点处的字段。

输出

第1行：一个整数，它是必须构建的新路径数。

package com.liuzhen.practice;

import java.util.ArrayList;

import java.util.Scanner;

import java.util.Stack;

public class Main {

    public static int n;  //给定图的顶点数

    public static int count;  //记录遍历次序

    public static int[] DFN;

    public static int[] Low;

    public static int[] parent;   //parent[i] = j，表示顶点i的直接父母顶点为j

    public static Stack<Integer> stack;

    public static ArrayList<edge>[] map;

    public static ArrayList<edge> ans;  //存储给定图中为桥的边

    static class edge {

        public int a;  //边的起点

        public int b;  //边的终点

        public boolean used;  //表示边是否已被访问

        public edge(int a, int b) {

            this.a = a;

            this.b = b;

            this.used = false;

        }

    }

    @SuppressWarnings("unchecked")

    public void init() {

        count = 0;

        DFN = new int[n + 1];

        Low = new int[n + 1];

        parent = new int[n + 1];

        stack = new Stack<Integer>();

        map = new ArrayList[n + 1];

        ans = new ArrayList<edge>();

        for(int i = 1;i <= n;i++) {

            DFN[i] = -1;

            Low[i] = -1;

            parent[i] = -1;

            map[i] = new ArrayList<edge>();

        }

    }

    public void TarJan(int start, int father) {

        DFN[start] = count++;

        Low[start] = DFN[start];

        parent[start] = father;

        stack.push(start);

        for(int i = 0;i < map[start].size();i++) {

            edge temp = map[start].get(i);

            if(temp.used)

                continue;

            int t = temp.b;

            for(int p = 0;p < map[t].size();p++) {

                if(map[t].get(p).b == temp.a) {

                    map[t].get(p).used = true;

                    break;

                }

            }

            temp.used = true;

            int j = temp.b;

            if(DFN[j] == -1) {

                TarJan(j, start);

                Low[start] = Math.min(Low[start], Low[j]);

                if(Low[j] > DFN[start])   //当边temp为割边(或者桥)时

                    ans.add(temp);

            } else if(j != parent[start]) {  //当j不是start的直接父母节点时

                Low[start] = Math.min(Low[start], DFN[j]);

            }

        }

    }

    public void getResult() {

        for(int i = 1;i <= n;i++) {

            if(parent[i] == -1)

                TarJan(i, 0);

        }

        int[] degree = new int[n + 1];

        for(int i = 0;i < ans.size();i++) {

            int a = ans.get(i).a;

            int b = ans.get(i).b;

            degree[a]++;

            degree[b]++;

        }

        int result = 0;

        for(int i = 1;i <= n;i++) {

            if(degree[i] == 1)

                result++;

        }

        result = (result + 1) / 2;

        System.out.println(result);

        return;

    }

    public static void main(String[] args) {

        Main test = new Main();

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        int m = in.nextInt();

        test.init();

        for(int i = 0;i < m;i++) {

            int a = in.nextInt();

            int b = in.nextInt();

            map[a].add(new edge(a, b));

            map[b].add(new edge(b, a));

        }

        test.getResult();

    }

}

运行结果：

巴特西

Java实现冗余路径Redundant Paths

最新文章

热门文章