Advertisement
VladislavSavvateev

Graphs: first part

Feb 25th, 2021
717
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.68 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Graphs {
  6.     internal static class Program {
  7.         public static void Main() {
  8.             if (!int.TryParse(Console.ReadLine(), out var n)) return;
  9.  
  10.             var list = new List<GraphPoint>();
  11.             for (var i = 0; i < n; i++) list.Add(new GraphPoint(i + 1));
  12.  
  13.             while (true) {
  14.                 var line = Console.ReadLine();
  15.                 if (string.IsNullOrEmpty(line)) break;
  16.  
  17.                 var parts = line.Split(' ').Select(p => (int.TryParse(p, out var val), val))
  18.                     .Where(p => p.Item1).Select(p => p.val).ToArray();
  19.  
  20.                 if (parts.Length != 2) continue;
  21.  
  22.                 var a = parts[0];
  23.                 var b = parts[1];
  24.                
  25.                 list[a - 1].Neighbours.Add(list[b - 1]);
  26.                 list[b - 1].Neighbours.Add(list[a - 1]);
  27.             }
  28.  
  29.             var chains = new List<List<GraphPoint>>();
  30.  
  31.             foreach (var t in list) {
  32.                 var neighboursList = new List<GraphPoint>();
  33.                 t.GetMeAndNeighbours(neighboursList);
  34.                 chains.Add(neighboursList.OrderBy(p => p.Value).ToList());
  35.             }
  36.            
  37.             chains = chains.Distinct(new GraphPoint.EqualityComparer()).ToList();
  38.            
  39.             Console.WriteLine(chains.Count - 1);
  40.         }
  41.  
  42.         public class GraphPoint {
  43.             public int Value { get; }
  44.             public List<GraphPoint> Neighbours { get; }
  45.  
  46.             public GraphPoint(int value) {
  47.                 Value = value;
  48.                 Neighbours = new List<GraphPoint>();
  49.             }
  50.  
  51.             public void GetMeAndNeighbours(List<GraphPoint> points) {
  52.                 if (points.Contains(this)) return;
  53.                 points.Add(this);
  54.  
  55.                 foreach (var point in Neighbours) point.GetMeAndNeighbours(points);
  56.             }
  57.  
  58.             public override int GetHashCode() => Value.GetHashCode() ^ Neighbours.GetHashCode();
  59.            
  60.             public override string ToString() { return Value.ToString(); }
  61.  
  62.             public class EqualityComparer : IEqualityComparer<List<GraphPoint>> {
  63.                 public bool Equals(List<GraphPoint> x, List<GraphPoint> y) {
  64.                     if (x == null && y == null) return true;
  65.                     if (x == null || y == null || x.Count != y.Count) return false;
  66.  
  67.                     return !x.Where((t, i) => t.Value != y[i].Value).Any();
  68.                 }
  69.  
  70.                 public int GetHashCode(List<GraphPoint> obj)
  71.                     => obj.Aggregate(0, (current, point) => current ^ point.GetHashCode());
  72.             }
  73.         }
  74.     }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement