Witam.
Jestem w trakcie pisania programu, który z założenia ma wypisywać ilość połączeń między "miastami", które nie są w cyklu.
Na wejściu podaję n i m, gdzie n to liczba węzłów(miast) a m to liczba połączeń między węzłami (miastami). Następnie podaje wszystkie połączenia podając dwa numery ID miast oddzielone spacją. Program na wyjściu powinien podawać liczbę połączeń, które, jeśliby zostały przerwane, to nie można by było przesłać informacji do kolejnych miast. Może zobrazowałby to poniższy przykładowy graf - na czerwono zaznaczyłem węzły, których ilość podawana jest na wyjściu.
Do tej pory sugerowałem się tym przykładem, napisałem kod działający, jednak zapomniałem o jednym istotnym elemencie, a mianowicie o tym, że cykl może składać się więcej niż z trzech elementów... Gdybyście mieli jakieś propozycje, jak sobie z tym poradzić.. Z góry wielkie dzięki za pomoc. :)
#include <iostream>
using namespace std;
int main ()
{
int m,n;
cin >> n >> m;
n = m;
int tab[m][3];
for (int i=0; i<m; i++)
{
cin >> tab[i][0] >> tab[i][1];
tab[i][2] = 0;
}
for (int i=0; i<m; i++)
{
for (int j=0; j<m; j++)
{
if ((tab[j][0] == tab[i][1] or tab[j][1] == tab[i][1]) and (tab[i][0] != tab[j][0] or tab[i][1] != tab[j][1]))
{
if (tab[j][1] == tab[i][1])
{
for (int k=0; k<m; k++)
{
if ((tab[j][0] == tab[k][0] or tab[j][0] == tab[k][1]) and (tab[k][0] == tab[i][0] or tab[k][1] == tab[i][0]))
{
if(tab[i][2] == 0)
{
n--;
}
tab[i][2]++;
}
}
}
else if (tab[j][0] == tab[i][1])
{
for (int k=0; k<m; k++)
{
if ((tab[j][1] == tab[k][0] or tab[j][1] == tab[k][1]) and (tab[k][0] == tab[i][0] or tab[k][1] == tab[i][0]))
{
if(tab[i][2] == 0)
{
n--;
}
tab[i][2]++;
}
}
}
}
}
}
/*
for (int i=0; i<m; i++)
{
cout << tab[i][0] << " " << tab[i][1] << " " << tab[i][2] << endl << endl;
}
*/
cout << n;
}