#include<stdio.h>
int GetMin(int n,int x,int max,bool note[][1010],short min[])
{
int m,result = n;
for(int i = 1;i<=max;i++)
{
if(i == x) continue;
if(note[n][i] == 1)
{
if(n == i) continue;
note[n][i] = note[i][n] = 0;
m = GetMin(i,x,max,note,min);
result = m < i? m:i;
note[n][i] = note[i][n] = 1;
}
}
return n>result? result:n;
}
int FindMin(int n,int x,int max,bool note[][1010],short min[])
{
for(int i = 1;i<=max;i++)
{
if(i == x) continue;
if(note[n][i] == 1)
{
if(min[i] == 0)
min[n] = min[i] = GetMin(i,x,max,note,min);
else
min[n] = min[i];
return min[n];
}
}
}
int main()
{
bool note[1010][1010] = {0};
short min[1010] = {0},min_num[1010] = {0};
int x = 1,y = 0,max = 0,count = 0,m,num = 0,flag,s_flag= 0,exit_flag = 1;
for(;;)
{
num++;
flag = 0;
count = 0;
max = 0;
s_flag = 0;
if(y != 0) printf("\n");
for(;;)
{
exit_flag = x;
scanf("%d",&x);
if(x == 0)
{
if(exit_flag == 0)
return 0;
break;
}
scanf("%d",&y);
max = x > max ? x : max;
max = y > max ? y : max;
note[x][y] = note[y][x] = 1;
}
for(int i = 1;i<=max;i++)
{
note[i][i] = 1;
}
printf("Network #%d\n",num);
for(int i = 1;i<=max;i++)
{
if(i == 1)
{
min[1] = 2;
min_num[0] = 2;
}
else
{
min[2] = 1;
min_num[0] = 1;
}
for(int j = 1;j<=max;j++)
{
if(j == i) continue;
m = FindMin(j,i,max,note,min);
for(int k = 0;k<=count;k++)
{
if(m == min_num[k])
{
flag = 1;
break;
}
}
if(!flag)
{
count++;
min_num[count] = m;
}
flag = 0;
}
if(count > 0)
{
s_flag = 1;
printf(" SPF node %d leaves %d subnets\n",i,count+1);
}
count = 0;
for(int j = 1;j<=max;j++)
{
min[j] = 0;
min_num[j] = 0;
}
}
if(!s_flag) printf(" No SPF nodes\n");
for(int i = 1;i<=max;i++)
for(int j = 1;j<=max;j++)
note[i][j] = 0;
}
return 0;
}
总是OLE
问题在http://acm.hit.edu.cn/problemset/1007
求指点