Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- namespace Graphs {
- internal static class Program {
- public static void Main() {
- if (!int.TryParse(Console.ReadLine(), out var n)) return;
- var list = new List<GraphPoint>();
- for (var i = 0; i < n; i++) list.Add(new GraphPoint(i + 1));
- while (true) {
- var line = Console.ReadLine();
- if (string.IsNullOrEmpty(line)) break;
- var parts = line.Split(' ').Select(p => (int.TryParse(p, out var val), val))
- .Where(p => p.Item1).Select(p => p.val).ToArray();
- if (parts.Length != 2) continue;
- var a = parts[0];
- var b = parts[1];
- list[a - 1].Neighbours.Add(list[b - 1]);
- list[b - 1].Neighbours.Add(list[a - 1]);
- }
- var chains = new List<List<GraphPoint>>();
- foreach (var t in list) {
- var neighboursList = new List<GraphPoint>();
- t.GetMeAndNeighbours(neighboursList);
- chains.Add(neighboursList.OrderBy(p => p.Value).ToList());
- }
- chains = chains.Distinct(new GraphPoint.EqualityComparer()).ToList();
- Console.WriteLine(chains.Count - 1);
- }
- public class GraphPoint {
- public int Value { get; }
- public List<GraphPoint> Neighbours { get; }
- public GraphPoint(int value) {
- Value = value;
- Neighbours = new List<GraphPoint>();
- }
- public void GetMeAndNeighbours(List<GraphPoint> points) {
- if (points.Contains(this)) return;
- points.Add(this);
- foreach (var point in Neighbours) point.GetMeAndNeighbours(points);
- }
- public override int GetHashCode() => Value.GetHashCode() ^ Neighbours.GetHashCode();
- public override string ToString() { return Value.ToString(); }
- public class EqualityComparer : IEqualityComparer<List<GraphPoint>> {
- public bool Equals(List<GraphPoint> x, List<GraphPoint> y) {
- if (x == null && y == null) return true;
- if (x == null || y == null || x.Count != y.Count) return false;
- return !x.Where((t, i) => t.Value != y[i].Value).Any();
- }
- public int GetHashCode(List<GraphPoint> obj)
- => obj.Aggregate(0, (current, point) => current ^ point.GetHashCode());
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement