Road construction issues

One   Original problem description

Road Construction - POJ 3352 - Virtual Judgehttps://vjudge.net/problem/POJ-3352

Two   Input and output

1  Input

Input the 1 Line includes positive integers n and r, among n Is the number of scenic spots ,r Is the number of roads . The number of tourist attractions is 1 To n , following r Each row in the row will consist of two integers v and w form , It means that v and w There are roads between the scenic spots . Please note that , The road is two-way , There is at most one road between any two tourist attractions . Besides , In the current configuration , You can travel between any two tourist attractions .

2 Output

The minimum number of roads to be added for single row output .

3、 ... and   Input and output samples

1  sample input

Sample Input 1

10 12

1 2

1 3

1 4

2 5

2 6

5 6

3 7

3 8

7 8

4 9

4 10

9 10

Sample Input 2

3 3

1 2

2 3

1 3

2  sample output

Output for Sample Input 1

2

Output for Sample Input 2

0

Four   analysis

1  Without adding edges  

sample input 2, The constructed figure is as follows . There is no need to add new roads , It can ensure that a road is repaired , You can reach any scenic spot by other roads . So you need to add 0 side .

2  Add multiple edges

If there is no bridge in an undirected graph , It is called edge biconnected graph . If a node is in an edge biconnected graph component , You don't need to add edges . Therefore, it is necessary to solve the edge biconnected components . You need to add edges between edge biconnected components . For example 1, Its edge double connected components are shown in the figure below .

Reduce each connected component to a point , As shown in the figure below

Solve the number of new roads that need to be added . If the degree is 1 The node of is k, At least (k+1)/2  side . for example , Yes 3 The individual degree is 1 At least two edges need to be added to the node of , Yes 4 The individual degree is 1 At least two edges need to be added to the node of .

Why count leaves （ Degree is 1 The node of ） Well ？ The connected component shrinks to get a tree , Adding an edge between any two points in the tree will produce a circuit . Add an edge between two leaves , Then leaves and some branch nodes form a loop . Add an edge between the branch nodes , The resulting circuit will not contain leaves . So by connecting leaves, you can add the fewest edges , Make every node in the circuit .

Why is the number of edges added (k+1)/2 Well ？ This should be divided into 1 Is the number of nodes odd or even , If it's even , It is k/2, If it's odd , It is (k+1)/2, Therefore, it is unified as (k+1)/2.

5、 ... and   Algorithm design

1  First run  Tarjan  Algorithm , Solve edge biconnected components .

2  Shrinkage point . Check each node  u  Every adjacent point of  v, if  low[u]!=low[v], Then this connected component point  low[u]  Du Jia of 1,degree[low[u]]++, Nodes in the same connected component  low The values are equal .

3 The statistical degree is 1 The number of points of is , That is, the number of leaf nodes , The least edges added are (leaf+1)/2.

6、 ... and   Code

package graph.poj3352;

import java.util.Scanner;

public class POJ3352 {
    static final int maxn = 1000 + 5;
    static int n;
    static int m;
    static int head[];
    static int cnt;
    static int root;
    static int low[];
    static int dfn[];
    static int degree[]; //  Degree of node 
    static int num;

    static Edge e[] = new Edge[maxn << 1];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    static void add(int u, int v) { //  Add an edge u--v
        e[++cnt].next = head[u];
        e[cnt].to = v;
        head[u] = cnt;
    }

    /**
     *  Function description ：tarjan  Algorithm 
     *
     * @param u   Start node 
     * @param fa  The parent node of the starting node 
     * @author cakin
     * @date 2022/7/3
     */
    static void tarjan(int u, int fa) { //  Find the edge biconnected component 
        dfn[u] = low[u] = ++num;

        for (int i = head[u]; i != 0; i = e[i].next) {
            int v = e[i].to;
            if (v == fa)
                continue;
            if (dfn[v] == 0) {
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);
            } else
                low[u] = Math.min(low[u], dfn[v]);
        }
    }

    static void init() {
        head = new int[maxn];
        low = new int[maxn];
        dfn = new int[maxn];
        degree = new int[maxn];
        cnt = num = 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            init();
            int u, v;
            while (m-- != 0) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                add(u, v);
                add(v, u);
            }
            tarjan(1, 0);
            for (u = 1; u <= n; u++)
                for (int i = head[u]; i != 0; i = e[i].next) {
                    v = e[i].to;
                    if (low[u] != low[v])
                        degree[low[u]]++;
                }
            int leaf = 0;
            for (int i = 1; i <= n; i++)
                if (degree[i] == 1)
                    leaf++;
            System.out.println((leaf + 1) / 2);
        }
    }
}

class Edge {
    int to;
    int next;
}

7、 ... and   test