- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
#include <stdio.h>
#define max(x,y) ((x>y)?x:y)
#define N 255
typedef unsigned char uchar;
uchar s,t,x,y,z,n,S[10000],FO[N+N*(N-1)/2];
uchar mask[]={1,2,4,8,16,32,64,128};
int TOP=0;
unsigned int COUNTER=0,AO[N];
FILE *in;
int pop(){
//if the top element in the stack is passed and stack is not empty,
//find next parent vertex
while(S[TOP]>128 && TOP>0) TOP-=S[TOP]-128;
return(TOP);
}
int push(){ //add new elements to the stack
int tmp=TOP,i,j,k; //tmp is a temporary variable
x=S[TOP-S[TOP]+1]; //x is a parent vertex
for(i=1;i<=FO[AO[x]];i++){
y=FO[AO[x]+i]; //y is a neigbour of x
if(!test(y)){ //y is visited? if not keep going
k=max(y/8+1,S[TOP]-2); //copy set P(x) to the new set P(y)
S[++tmp]=y;
for(j=0;j<k;j++,S[++tmp]=0);
S[++tmp]=k+2;
for(j=1;j<=S[TOP]-2;j++) S[tmp-j]=S[TOP-j];
S[tmp-(y/8+1)]|=mask[y-(y/8)*8]; //add child y to P(y)
}
}
S[TOP]+=128; //drop flag for the vertex x
TOP=tmp; //the last child y become parent
}
int test(int j){ //does vertex j in the set P(TOP)?
z=((j/8+1)>S[TOP]-2)?0:(S[TOP-(j/8+1)] & mask[j-(j/8)*8])?1:0;
return(z);
}
int inc(){ //the path was found
COUNTER++;
S[TOP]+=128;
}
int main(){
int i,j,k;
in=fopen("Data15.txt","r"); //open file
fscanf(in," %d %d",&i,&n); //read the number of vertices
for(k=n,i=0;k>=0;k--){
fscanf(in,"%d %d",&j,&FO[i]);
j=FO[i];
for(AO[n-k]=++i-1;j>0;j--,i++){
fscanf(in,"%d ",&FO[i]);
}
}
printf("Type first and end nodes: "); //type s and t separated by space
scanf("%d %d",&s,&t);
S[0]=s;
for(j=1;j<=s/8+1;S[j++]=0);
S[j]=s/8+3;
TOP=j;
S[TOP-(s/8+1)]|=mask[s-(s/8)*8];
while(pop()>=0) (test(s) && test(t))?inc():push(); //launch breadth-search algorithm
printf("# of paths in the graph b/w s=%d and t=%d equals %d\n",s,t,COUNTER);
return(0);
}
разбирая старый CD бэкап откопал лабу...(знаю,знаю что продакшн кошернее, и на сях не пишу со студенчества)
хотел вайпнуть безжалости но вспомнил про говнокодосайт.
помоему код люто доставляет.
прога подсчитывает полное число путей в графе между заданными вершинами s и t.
граф считывается из файла в формате: "номер_вершины степень_вершины {достижимые_вершины_через_пробел}"
(по коду видно)
Follow us!