結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2020-10-09 22:31:57 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 340 ms / 2,000 ms |
コード長 | 3,234 bytes |
コンパイル時間 | 3,076 ms |
コンパイル使用メモリ | 108,416 KB |
実行使用メモリ | 74,932 KB |
最終ジャッジ日時 | 2024-07-20 12:54:39 |
合計ジャッジ時間 | 21,506 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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(); } }