nyist120 校园网络 (Tarjan算法 / 强连通分量)

举报
楚楚冻人玥玥仙女 发表于 2021/11/19 02:53:52 2021/11/19
【摘要】 校园网络(nyist 120) 解题思路请看代码块中的注释~ import java.util.Scanner; import java.util.Stack; import java.util.V...

校园网络(nyist 120

解题思路请看代码块中的注释~


import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

/**考点:强连通分量
 * 考查算法:Tarjan算法
 * 解析:
 * 本题需要求给定的有向图中有多少个强连通分量,
 * 然后将强连通分量缩点,
 * 最后求缩点后的有向无环图中,
 * 需要添加多少条边,
 * 可以再次生成一个强连通图
 * 添加的边数为缩点后的有向无环图的出度为0的点的个数与入度为0的点的个数的最大值
 * 即 MAX(zeroOutNumber,zeroInNumber)
 * 当缩点后只有一个点时,需要特判一下,即输出结果就是0,不需要添加边
 */
public class NYIST120强连通分量 {
    static Vector<Integer>[]vectors;
    static int[]dfn,low,vis,components;
    static int num, componentNumber;
    static Stack<Integer>stack;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-->0){
            int n = scanner.nextInt();
            vectors = new Vector[n+1];
            componentNumber = 0;
            for (int  i = 1; i <= n; i++){
                vectors[i] = new Vector<Integer>();
                int x = scanner.nextInt();
                while (x != 0){
                    vectors[i].add(x);
                    x = scanner.nextInt();
                }
            }
            stack = new Stack<Integer>();
            dfn = new int[n+1];
            low = new int[n+1];
            vis = new int[n+1];
            components = new int[n+1];
            num = 0;
            for (int i = 1; i <= n; i++){
                if (dfn[i]==0){
                    Tarjan(i);
                }
            }
            if (componentNumber == 1){
                System.out.printf("0\n");
                continue;
            }
            int []out = new int[componentNumber+1];
            int []in = new int[componentNumber+1];
            for (int i = 1;  i<= n; i++){
                for (Integer v: vectors[i]){
                    if (components[i] != components[v]){
                        out[components[i]]++;
                        in[components[v]]++;
                    }
                }
            }
            int zeroOutNumber = 0, zeroInNumber = 0;
            for (int  i = 1; i <= componentNumber; i++){
                if (out[i] == 0)
                    zeroOutNumber ++;
                if (out[i] == 0)
                    zeroInNumber ++;
            }
            System.out.print(String.format("%d\n",Math.max(zeroOutNumber, zeroInNumber)));
        }
    }

    private static void Tarjan(int u) {
        dfn[u] = low[u] = ++num;
        stack.add(u);
        vis[u] = 1;
        for (int i = 0; i < vectors[u].size(); i++){
            int v = vectors[u].get(i);
            if (dfn[v] == 0){
                Tarjan(v);
                low[u] = Math.min(low[u],low[v]);
            }
            else if (vis[v] == 1){
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
        if (low[u] == dfn[u]){
            int temp;
            componentNumber++;
            do {
                temp = stack.pop();
                vis[temp] = 0;
                components[temp] = componentNumber;
            }while (temp != u);
        }
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99

文章来源: blog.csdn.net,作者:爱玲姐姐,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/jal517486222/article/details/80404574

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200