Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Проверка связанности графа

Автор: Sailes 6.1.2007, 16:34

Помогите написать программу.
Такая задача:

В заданной группе людей некоторые попарно дружат. В этой группе все люди дружественны, то есть любые двое или сами являются друзьями, или их друзья дружат, или друзья их друзей дружат и т.д.
Найти все такие пары, что если их поссорить, то получится два недружественных лагеря.

Если перевести все это на русский язык, то получится

Есть граф с заданным числом вершин и ребер. Граф связанный (из одной вершины можно пройти в любую другую). Нужто найти все такие ребра, при удалении которых связанность нарушается.

Собственно, вот.

Автор: Sailes 15.1.2007, 16:32

Эх, что-то тихо в топике... Разгоню молчание.
В общем, откопал прогу (прикрепленный файл), она оооочень большая и ооочень сложная (для меня), но в ней содержатся алгоритмы, необходимые для решения задачи в после выше, а именно - с помощью списков смежности создается граф (для каждой вершины в порядке возрастания указываются вершины, с которыми она соприкасается ребрами), а также алгоритм
удаления ребра,
пути из выбранной вершины в другую выбранную вершину и
пути из выбранной вершины во все остальные.
А не мог бы кто-нибудь посмотреть, как реализовать проверку всех путей из всех вершин во все остальные вершины после удаления ребра? То есть как раз связанность?
Народ, плиз, отзовитесь пожалуйста. smile

Автор: VaiMR 21.1.2007, 13:36

Вот, собственно, проверка связности:

Код


int graf[maxkolv][maxkolv];
    kolv;//=4;
int *gr[]={(int*)&graf[0],
           (int*)&graf[1],
           (int*)&graf[2],
           (int*)&graf[3],
           (int*)&graf[4],
           (int*)&graf[5],
           (int*)&graf[6],
           (int*)&graf[7],
           (int*)&graf[8],
           (int*)&graf[9],
           };

//================ проверка связности =====================

//-----Проверка наличия вершин помеченных 2 маркером-------
char kolv2(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]==2)
    return 't';
  return 'f';
 }
//---------------------------------------------------------

char svaz(int kolv,int *gr[])
{
 int mbuf[maxkolv];

 for (int i=0;i<kolv;i++)
  mbuf[i]=1;

 mbuf[1]=2;
 while (kolv2(kolv,mbuf)=='t')
  for (i=0;i<kolv;i++)
   if (mbuf[i]==2)
    {
     mbuf[i]=3;
      for (int j=0;j<kolv;j++)
       if ((gr[i][j]==1)&&(mbuf[j]==1))
    mbuf[j]=2;
    };
 for (i=0;i<kolv;i++)
  if (mbuf[i]==1)
   return 'f';
 return 't';
}
//=========================================================