Графы на С++

#include <iostream.h>
#include <Windows.h>
#include <iomanip>
#include <process.h> 
 
int kol_par, i, first, gl, count, **mas1; 
int main ()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî çíàêîìûõ ïàð"<<endl;
    cin>>kol_par;
    mas1=new int*[kol_par];
    for(i=0; i<kol_par; i++)
        mas1[i]=new int[2];
    cout<<"Ââåäèòå çíàêîìûå ïàðû"<<endl;
    for(i=0; i<kol_par; i++)
        cin>>mas1[i][0]>>mas1[i][1];
    cout<<"íóæíî ïîçíàêîìèòü:"<<endl;
    count=0;
    first=gl=mas1[0][0];
    int a;
    do
    {
        for(i=0; i<kol_par; i++)
        {
            if(mas1[i][0]==gl)
                mas1[i][0]=-1;
            if(mas1[i][1]==gl)
                mas1[i][1]=-1;
        }
        a=0;
        for(i=0; i<kol_par; i++)
        {
            if(mas1[i][0]==-1 && mas1[i][1]!=-1)
            {
                gl=mas1[i][1];
                a=1;
                break;
            }
            if(mas1[i][0]!=-1 && mas1[i][1]==-1)
            {
                gl=mas1[i][0];
                a=1;
                break;
            }
        }
        if(a==0)
        {
            for(i=0; i<kol_par; i++)
                if(mas1[i][0]!=-1)
                {
                    gl=mas1[i][0];
                    cout<<first<<"   "<<gl<<endl;
                    count++;
                    break;
                }
 
        }
        a=0;
        for(i=0; i<kol_par; i++)
            if(mas1[i][0]!=-1 || mas1[i][1]!=-1)
                a=1;
    }while(a==1);
        cout<<"Êîëè÷åñòâî ïàð íóæíî ïîçíàêîìèòü: "<<count<<endl;
    system("pause");
    return 0;
}

#include <stdio.h>
#include <iostream>
using namespace std;
 
 
int main(){
 
 int kol_studentov;
 
 //Это вот один и второй, будем их вводить.
 int odin;
 int vtoroi;
 
 //Вот по этой переменной мы либо выходим из цикла, либо нет. 
 char vihod_i_tsikla;
 
 //Эта штука будет содержать информацию о студенте.
 //Адрес нулевого элемента это адрес нулевого элемента
 //списка, к которому принадлежит студент
 //если адрес указывает в никуда, студнт не принадлежит ни одному из списков
 struct student {
  student* adres_nachalnogo_elementa;
  student* adres_ego_druga;
 }*pstudent;
 
 
 
 cout<<"Вводи количество студентов"<< endl;
 cin>> kol_studentov;
 
 
 
 
 //Это вот под студентов мы объявляем массив
 student* pMassivStudentov= new student [kol_studentov]; 
 
 
 //Все элементы будем обнулять принудительно. Это очень важно!
 for (int i= 0; i< kol_studentov;i++ ) {
  pMassivStudentov[i].adres_nachalnogo_elementa= 0;
  pMassivStudentov[i].adres_ego_druga= 0;
 }
 printf ("&pMassivStudentov[0]=  %d\n\n", &pMassivStudentov[0]);
 
 
 
 //Будем формировать связные списки.
 //По окончании задачи нас будет интересовать только один какой-нибудь 
 //элемент каждого связного списка
 //Допустим, организовалось 5 групп (5 связных списков) и 3 свободных студента
 //Пусть номера ПОСЛЕДНИХ (почему последних- объяснение внизу.) элементов в связных списках 1, 2, 34, 23, 5
 //Пусть номера свободных студентов 7, 20, 56
 //Тогда вот тебе минимальное количество пар-знакомств, чтобы все были знакомы друг с другом.
 //1- 2, 2-34, 34- 23, 23- 5, 5- 7, 7-20, 20-56
 
 //Главное- правильно заполнить массив pMassivStudentov
 //В путь!
 
 
 while (1) {
 
  cout<< "Вводи пару"<< endl;
  cin>>odin;
  cin>>vtoroi;
   
  //Рассмотрим имеющиеся у нас связные списки и наличие в них первогои второго студентов
  //Варианты: 
  //1) если студенты не присутствуют ни в каких списках, составляем из них
  //новый связный список
  //2) ЕСли студенты присутствуют в одном каком-нибудь списке, то ничё не делем.
  //3) если студенты присутствуют в разных списках, "соединяем эти списки"
  //4) Если какой-то из студентов присутствует в каком-нибудь списке, то присоединяем второго
  //к этому списку
  //фишка в том, что ни один студент не может присутствовать более, чем в одном связном списке
 
    
  //Теперь вопрос- как узнать, принадлежит студент к какому-нибудь связному списку?
  //Правильно, надо посмотреть на adres_nachalnogo_elementa
  //на поле adres_ego_druga смотреть не надо, т. к. если чел последним в списке, то
  //оно также будет указыватьв никуда, как если бы он ни в каком списке не состоял
  
  //сюда идём, если первый чел состоит в каком-нибудь связном списке
  if (pMassivStudentov[odin].adres_nachalnogo_elementa) {
 
   //Cюда идём, если второй чел состоит в этом же связном списке
   if (pMassivStudentov[odin].adres_nachalnogo_elementa==pMassivStudentov[vtoroi].adres_nachalnogo_elementa) {
    //Кстати, тут ничё делать не надо. Исправлять не буду. Зато иллюстративно
   }
 
   //сюда идём, если второй чел не стостоит в том списке, что и первый.
   //кстати, не факт, что второй состоит в каком-нибудь списке
   else     {
 
    //Сюда идём, если второй чел состоит в списке, отличным от того, в каком состоит первый
    //Тут фишка в том, что если он вобще
    //нигде не состоит, то выполняются одни и те же действия, как если бы он состоял в 
    //каком-нибудь списке ВоТ они
    //Значит, их надо запихать в один список. Соединить то есть списки.
    //делаем это так
    //Берём список, которому принадлежит студент odin и добираемся до его последнего элемента
    //И вот здесь нам понадобится pstudent
    pstudent= &pMassivStudentov[odin];
    while (pstudent->adres_ego_druga)
     pstudent=pstudent->adres_ego_druga;
 
    //Всё, теперь pstudent указыват на последний элемент в списке
    //Теперь делаем так
    pstudent->adres_ego_druga= &pMassivStudentov[vtoroi];
      
    //Всё, связный список сформирован
    //Теперь в элементах, что раньше принадлежали второй половине списка, исправим поля
    //adres_nachalnogo_elementa и всё на этом
    pstudent= &pMassivStudentov[vtoroi];
    pstudent->adres_nachalnogo_elementa= pMassivStudentov[odin].adres_nachalnogo_elementa;
    while (pstudent->adres_ego_druga) {
     pstudent=pstudent->adres_ego_druga;
     pstudent->adres_nachalnogo_elementa= pMassivStudentov[odin].adres_nachalnogo_elementa;
    }
    ; 
 
   }
  }   
 
  //а сюда идём, если не состоит (первый)
  else {
 
   //сюда пойдём, если второй чел состоит в каком-нибудь списке
   if (pMassivStudentov[vtoroi].adres_nachalnogo_elementa) {
    //Действия описывать не буду, они уже выше описаны, толко там наоборот было
    //Первый состоял в спписке. а второй нет
    pstudent= &pMassivStudentov[vtoroi];
    while (pstudent->adres_ego_druga)
     pstudent=pstudent->adres_ego_druga;
    pstudent->adres_ego_druga= &pMassivStudentov[odin];
    pstudent= &pMassivStudentov[odin];
    pstudent->adres_nachalnogo_elementa= pMassivStudentov[vtoroi].adres_nachalnogo_elementa;
    while (pstudent->adres_ego_druga) {
     pstudent=pstudent->adres_ego_druga;
     pstudent->adres_nachalnogo_elementa= pMassivStudentov[vtoroi].adres_nachalnogo_elementa;
    }
   }
 
   //а сюда пойдём, если не состоит ни тот, ни другой
   //значит, формируем из них двух связный список
   else {
    pMassivStudentov[odin].adres_nachalnogo_elementa=&pMassivStudentov[odin];
    pMassivStudentov[odin].adres_ego_druga=&pMassivStudentov[vtoroi];
    pMassivStudentov[vtoroi].adres_nachalnogo_elementa=&pMassivStudentov[odin];
   }
  } 
  
 
 
  //Так, здесь смотрим, будем вводить дальше пару или нет
  cout<< "Работаем дольше? (y или любой другой знак)"<< endl;
  fflush (stdin);
  if (vihod_i_tsikla= getchar ()!= 'y') 
   break;
 }
 
 //Всё. Теперь пробегаемя по всем связным спискам и из каждого берём по одному студенту.
 //Делается это так.
 //Только у последних студентов всех связных списков поле adres_ego_druga
 //указывает в никуда
 //Кроме того,в никуда оно указывает и у всех свободных студентв
 //Короче,  берём тех студентов, у уоторых это поле указывает в никуда, знакомими
 //их меж собой и всё, аля-улю, гони гусей.
 
 cout<< "Лови номера студентов. Ты их уж перезнакомь как-нибудь сам..."<< endl;
 
 for (int i= 0; i< kol_studentov; i++) {
  if (!pMassivStudentov[i].adres_ego_druga) {
   printf ("%d   ", i);
  }
 }
 printf ("\n");
 getchar ();
 getchar ();
 return 0;
}