VladislavSavvateev

Graphs: first part

Feb 25th, 2021
531
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×