Граф и компоненты связности - C#

Узнай цену своей работы

Формулировка задачи:

Дан граф, который состоит из нескольких компонентов связности. Найти компоненты связности, пронумеровать их, вершину отнести к тому номеру компонента связности, в который она попадает. ВХОД: Список рёбер. На каждой строке № вершины, разделённые пробелом (это означает, что между этими вершинами есть ребро). По одному ребру на каждой строке. ВЫХОД: На каждой строке: вершина; пробел; номер компонента связности (начиная с нуля), к которому эта вершина относится. вот такое вот задание у меня в универе. может кто написать код? а то сам я не бум бум. А сдавать уже надо.

Решение задачи: «Граф и компоненты связности»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var fr = File.ReadAllLines("read.txt");
            var edges =
                fr.Select(s => s.Split(' '))
                    .Select(temp => new Edge {V1 = int.Parse(temp[0]), V2 = int.Parse(temp[1])})
                    .ToList();
            var vertices = new List<int>();
            foreach (var e in edges)
            {
                if (!vertices.Contains(e.V1)) vertices.Add(e.V1);
                if (!vertices.Contains(e.V2)) vertices.Add(e.V2);
            }
            using (var sw = new StreamWriter("write.txt"))
            {
                foreach (var v in vertices)
                {
                    sw.Write(v + " ");
                    for (var i = 0; i < edges.Count; i++)
                    {
                        if (v == edges[i].V1 || v == edges[i].V2) sw.Write(i + " ");
                    }
                    sw.WriteLine();
                }
            }
        }
    }
 
    class Edge
    {
        public int V1 { get; set; }
        public int V2 { get; set; }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.833 из 5
Похожие ответы