Int main(int argc, char* argv[])

{

ifstream in("in_poisk_v_shirinu.txt");

in>>n;

mas=new int*[n];

P=new int[n];

pre=new int[n];

for(int i=0;i<=n-1;++i) mas[i]=new int[n];

for(int i=0;i<=n-1;++i) for(int j=0;j<=n-1;++j) in>>mas[i][j];

for(int i=0;i<=n-1;++i) {P[i]=0;pre[i]=0;}

for(int i=0;i<=n-1;++i) if(pre[i]==0) bfs(i);

}

24. Написать программу, выполняющую топологическую сортировку заданного ациклического ориентированного графа.

int **A;

int n;

int *pre;

int *P;

int *post;

int NumPre=0;

int NumPost=0;

void dfs(int v)

{

NumPre++;

pre[v]=NumPre;

for(int i=0;i<=n-1;++i) if ((A[v][i]>0) && (pre[i]==0))

{

P[i]=v;

dfs(i);

}

NumPost++;

post[v]=NumPost;

}

Int main(int argc, char* argv[])

{

fstream in("in_poisk_v_glubinu.txt");

in>>n;

A=new int*[n];

P=new int[n];

pre=new int[n];

post=new int[n];

for(int i=0;i<=n-1;++i) A[i]=new int[n];

for(int i=0;i<=n-1;++i) for(int j=0;j<=n-1;++j) in>>A[i][j];

for(int i=0;i<=n-1;++i) {P[i]=0;pre[i]=0;post[i]=0;}

for(int i=0;i<=n-1;++i) if(pre[i]==0) dfs(i);

for(int i=0;i<=n-1;++i) cout<<post[i]<<" ";

}

25. Написать программу, находящую максимальное паросочетание в заданном двудольном графе.

int p[10];

int V[10];

int g1, g2, m;

int A[10][10];

int Tr(int X)

{

int t = 0;

if (!V[X])

{V[X] = 1;

for (int k = 0; k < g2; k++)

if (A[X][k] == 1 && (p[k] == -1 || Tr(p[k]))){

p[k]=X;

t = 1;

break;

}}

return t;

}

int main()

{

ifstream in("1.txt");

in >> g1 >> g2 >> m;

for (int i = 0; i < g1; i++)

{for (int j = 0; j < g1; j++)

A[i][j] = 0; }

int temp1, temp2;

for (int i = 0; i < m; i++)

{in >> temp1 >> temp2;

A[temp1-1][temp2-1] = 1;

}

for (int i = 0; i < g1; i++)p[i] = -1;

for (int i = 0; i < g1; i++){

for (int j = 0; j < g1; j++) V[j]=0;

Tr(i);

}

cout<< "Max parosoch : "<<endl;

for (int i = 0; i < g2; i++)

if (p[i] != -1)

cout << i+1 << '-' << p[i] + 1 << endl;

cout << endl;

char ch;

cin>> ch;

}