結果

問題 No.1254 補強への架け橋
ユーザー 👑 箱
提出日時 2020-10-09 22:31:57
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 3,234 bytes
コンパイル時間 3,931 ms
コンパイル使用メモリ 106,096 KB
実行使用メモリ 79,044 KB
最終ジャッジ日時 2023-09-27 18:26:04
合計ジャッジ時間 28,517 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
24,852 KB
testcase_01 AC 72 ms
22,684 KB
testcase_02 AC 68 ms
22,828 KB
testcase_03 AC 68 ms
24,792 KB
testcase_04 AC 68 ms
24,780 KB
testcase_05 AC 68 ms
26,852 KB
testcase_06 AC 71 ms
24,780 KB
testcase_07 AC 73 ms
24,688 KB
testcase_08 AC 74 ms
24,832 KB
testcase_09 AC 70 ms
26,792 KB
testcase_10 AC 70 ms
24,756 KB
testcase_11 AC 69 ms
24,808 KB
testcase_12 AC 69 ms
26,848 KB
testcase_13 AC 73 ms
24,732 KB
testcase_14 AC 72 ms
26,924 KB
testcase_15 AC 70 ms
26,752 KB
testcase_16 AC 69 ms
26,824 KB
testcase_17 AC 75 ms
26,732 KB
testcase_18 AC 68 ms
22,804 KB
testcase_19 AC 69 ms
24,848 KB
testcase_20 AC 71 ms
24,864 KB
testcase_21 AC 69 ms
24,764 KB
testcase_22 AC 71 ms
24,944 KB
testcase_23 AC 70 ms
24,784 KB
testcase_24 AC 70 ms
22,856 KB
testcase_25 AC 72 ms
24,864 KB
testcase_26 AC 73 ms
24,840 KB
testcase_27 AC 73 ms
26,824 KB
testcase_28 AC 74 ms
24,708 KB
testcase_29 AC 73 ms
24,780 KB
testcase_30 AC 71 ms
24,788 KB
testcase_31 AC 72 ms
24,904 KB
testcase_32 AC 69 ms
24,652 KB
testcase_33 AC 73 ms
24,852 KB
testcase_34 AC 75 ms
24,636 KB
testcase_35 AC 69 ms
24,588 KB
testcase_36 AC 71 ms
22,808 KB
testcase_37 AC 69 ms
24,844 KB
testcase_38 AC 69 ms
22,676 KB
testcase_39 AC 70 ms
26,724 KB
testcase_40 AC 73 ms
24,776 KB
testcase_41 AC 71 ms
26,692 KB
testcase_42 AC 71 ms
26,812 KB
testcase_43 AC 71 ms
26,684 KB
testcase_44 AC 73 ms
26,764 KB
testcase_45 AC 69 ms
26,736 KB
testcase_46 AC 71 ms
26,676 KB
testcase_47 AC 70 ms
26,720 KB
testcase_48 AC 71 ms
24,880 KB
testcase_49 AC 71 ms
24,692 KB
testcase_50 AC 73 ms
26,728 KB
testcase_51 AC 71 ms
26,836 KB
testcase_52 AC 69 ms
24,848 KB
testcase_53 AC 70 ms
24,728 KB
testcase_54 AC 73 ms
24,720 KB
testcase_55 AC 83 ms
24,788 KB
testcase_56 AC 72 ms
24,740 KB
testcase_57 AC 70 ms
24,888 KB
testcase_58 AC 74 ms
24,732 KB
testcase_59 AC 71 ms
22,804 KB
testcase_60 AC 71 ms
24,868 KB
testcase_61 AC 69 ms
24,792 KB
testcase_62 AC 72 ms
24,772 KB
testcase_63 AC 95 ms
36,284 KB
testcase_64 AC 77 ms
22,792 KB
testcase_65 AC 88 ms
31,688 KB
testcase_66 AC 83 ms
29,640 KB
testcase_67 AC 74 ms
26,720 KB
testcase_68 AC 82 ms
27,528 KB
testcase_69 AC 84 ms
31,360 KB
testcase_70 AC 78 ms
29,024 KB
testcase_71 AC 75 ms
24,824 KB
testcase_72 AC 90 ms
31,484 KB
testcase_73 AC 77 ms
24,720 KB
testcase_74 AC 91 ms
31,476 KB
testcase_75 AC 80 ms
27,736 KB
testcase_76 AC 72 ms
24,704 KB
testcase_77 AC 79 ms
29,576 KB
testcase_78 AC 92 ms
32,288 KB
testcase_79 AC 94 ms
34,200 KB
testcase_80 AC 90 ms
33,264 KB
testcase_81 AC 97 ms
34,196 KB
testcase_82 AC 88 ms
29,444 KB
testcase_83 AC 339 ms
68,908 KB
testcase_84 AC 343 ms
66,792 KB
testcase_85 AC 234 ms
52,272 KB
testcase_86 AC 305 ms
61,620 KB
testcase_87 AC 316 ms
64,212 KB
testcase_88 AC 104 ms
34,564 KB
testcase_89 AC 334 ms
67,916 KB
testcase_90 AC 246 ms
53,672 KB
testcase_91 AC 213 ms
48,632 KB
testcase_92 AC 134 ms
40,492 KB
testcase_93 AC 286 ms
58,036 KB
testcase_94 AC 267 ms
53,636 KB
testcase_95 AC 263 ms
57,652 KB
testcase_96 AC 361 ms
63,316 KB
testcase_97 AC 197 ms
50,192 KB
testcase_98 AC 344 ms
67,952 KB
testcase_99 AC 227 ms
49,776 KB
testcase_100 AC 354 ms
67,668 KB
testcase_101 AC 129 ms
39,920 KB
testcase_102 AC 100 ms
32,260 KB
testcase_103 AC 131 ms
40,692 KB
testcase_104 AC 156 ms
43,056 KB
testcase_105 AC 284 ms
55,844 KB
testcase_106 AC 194 ms
49,272 KB
testcase_107 AC 341 ms
68,860 KB
testcase_108 AC 353 ms
64,008 KB
testcase_109 AC 264 ms
57,788 KB
testcase_110 AC 252 ms
53,696 KB
testcase_111 AC 269 ms
55,544 KB
testcase_112 AC 151 ms
42,188 KB
testcase_113 AC 246 ms
52,268 KB
testcase_114 AC 183 ms
48,312 KB
testcase_115 AC 107 ms
32,156 KB
testcase_116 AC 210 ms
50,520 KB
testcase_117 AC 151 ms
43,248 KB
testcase_118 AC 333 ms
65,432 KB
testcase_119 AC 218 ms
48,656 KB
testcase_120 AC 327 ms
65,424 KB
testcase_121 AC 142 ms
40,160 KB
testcase_122 AC 205 ms
54,180 KB
testcase_123 AC 67 ms
24,716 KB
testcase_124 AC 369 ms
79,008 KB
testcase_125 AC 378 ms
79,044 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

public class Solution
{
    private IList<int>[] graph;
    private bool[] visited;
    private int[] visitedTimes;
    private int[] lowVisitedTimes;
    private IList<IList<int>> criticalConnections;
    private int time;

    public IList<IList<int>> CriticalConnections(int n, IList<IList<int>> connections)
    {
        graph = new IList<int>[n];
        visited = new bool[n];
        visitedTimes = new int[n];
        lowVisitedTimes = new int[n];
        criticalConnections = new List<IList<int>>();
        time = 0;

        InitGraph(n, connections);
        DFS(0, -1);

        return criticalConnections;
    }

    private void DFS(int current, int parent)
    {
        visited[current] = true;
        visitedTimes[current] = lowVisitedTimes[current] = time++;

        foreach (var server in graph[current])
        {
            if (server == parent)
            {
                continue;
            }

            if (!visited[server])
            {
                DFS(server, current);
                if (visitedTimes[current] < lowVisitedTimes[server])
                {
                    criticalConnections.Add(new List<int>(2) { current, server });
                }
                else if (visitedTimes[current] > lowVisitedTimes[server])
                {
                    lowVisitedTimes[current] = lowVisitedTimes[server];
                }
            }
            else
            {
                lowVisitedTimes[current] = Math.Min(lowVisitedTimes[current], visitedTimes[server]);
            }
        }
    }

    private void InitGraph(int n, IList<IList<int>> connections)
    {
        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<int>();
        }

        foreach (var connection in connections)
        {
            var a = connection[0];
            var b = connection[1];
            graph[a].Add(b);
            graph[b].Add(a);
        }
    }
}

class MyClass
{
    public static void Solve()
    {
        var N = int.Parse(Console.ReadLine());
        var edges = new List<IList<int>>();
        var dic = new Dictionary<(int, int), int>();
        for (int i = 0; i < N; i++)
        {
            var data = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var A = data[0] - 1;
            var B = data[1] - 1;
            var edge = new List<int>();
            edge.Add(A);
            edge.Add(B);
            edges.Add(edge);
            dic.Add((A, B), i + 1);
            dic.Add((B, A), i + 1);
        }
        var sol = new Solution();
        var pri = sol.CriticalConnections(N, edges);
        var ans = Enumerable.Range(1, N).ToHashSet();
        foreach (var item in pri)
        {
            var A = item[0];
            var B = item[1];
            ans.Remove(dic[(A, B)]);
        }
        Console.WriteLine(ans.Count());
        Console.WriteLine(string.Join(" ", ans));
    }

    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}
0