03/15 - Hungary's Day - Mr. Lee's Algorithm

Să se determine lungimea minimă a lanţurilor de la un nod oarecare la toate celelalte.

#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
int n,m,a[100][100],viz[100],lg[100],c[100];
void citire()
{int x,y;
ifstream f("date");
f>>n>>m;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
}

void LEE(int start)
{int st=1,dr=1,varf,i;
c[st]=start;
viz[start]=1;
lg[start]=0;
while(st<=dr)
{varf=c[st];
for(i=1;i<=n;i++)
    if(a[i][varf]==1)
        if(viz[i]==0)
        {c[++dr]=i;
        viz[i]=1;
        lg[i]=lg[varf]+1;}
        st++;
}
}

int main()
{citire();
int start,i;
cout<<"Cititi nodul de start"<<endl;
cin>>start;
LEE(start);
cout<<"Lungimile minile ale lanturilor care pornesc din "<<start<<endl;
for(i=1;i<=n;i++)
    cout<<"catre "<<i<<": "<<lg[i]<<endl;
}

Fişier

9 11
1 2
1 3
1 4
2 4
2 5
2 7
2 8
3 4
3 6
4 5
8 9