結果
問題 | No.2072 Anatomy |
ユーザー |
|
提出日時 | 2022-09-16 23:07:22 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 2,652 bytes |
コンパイル時間 | 4,295 ms |
コンパイル使用メモリ | 112,564 KB |
実行使用メモリ | 83,540 KB |
最終ジャッジ日時 | 2024-12-21 22:39:01 |
合計ジャッジ時間 | 9,854 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();static void Main(){Solve();}static void Solve(){var c = NList;var (n, m) = (c[0], c[1]);var map = NMap(m);var tree = new List<int>[m];for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>();var uf = new UnionFindTree(n);var isBridge = new bool[m];for (var i = m - 1; i >= 0; --i){var pa = uf.info[uf.GetRoot(map[i][0])];var pb = uf.info[uf.GetRoot(map[i][1])];if (pa != int.MaxValue) tree[i].Add(pa);if (pb != int.MaxValue && pb != pa) tree[i].Add(pb);uf.Unite(map[i][0], map[i][1], i);}var dep = new int[m];DFS(0, tree, dep);WriteLine(dep.Max() + 1);}static void DFS(int cur, List<int>[] tree, int[] dep){foreach (var next in tree[cur]){dep[next] = dep[cur] + 1;DFS(next, tree, dep);}}class UnionFindTree{int[] roots;public int[] info;public UnionFindTree(int size){roots = new int[size];info = Enumerable.Repeat(int.MaxValue, size).ToArray();for (var i = 0; i < size; ++i) roots[i] = -1;}public int GetRoot(int a){if (roots[a] < 0) return a;roots[a] = GetRoot(roots[a]);info[roots[a]] = Math.Min(info[roots[a]], info[a]);return roots[a];}public bool IsSameTree(int a, int b){return GetRoot(a) == GetRoot(b);}public bool Unite(int a, int b, int info){var x = GetRoot(a);var y = GetRoot(b);this.info[x] = Math.Min(this.info[x], info);this.info[y] = Math.Min(this.info[y], info);if (x == y) return false;if (-roots[x] < -roots[y]) { var tmp = x; x = y; y = tmp; }roots[x] += roots[y];roots[y] = x;return true;}public int GetSize(int a){return -roots[GetRoot(a)];}}}