Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## TLE，牛人指点下啊！谢谢了！

Posted by yogafrank at 2008-07-16 00:39:44 on Problem 3631
```# include < stdio.h >
# include < string.h >

typedef struct
{
int hash1;
int hash2;
}Hash;

Hash hash[10000];
int tab[10000];
int x, y;

//当前冲突的单元 and 要放进的值
int solve ( int slot, int value )
{
int temp;

temp = tab[slot];
tab[slot] = value;

//被替换区域任何一个可以使用则将被替换的放入
if ( tab[hash[temp-1].hash1] == 0 )
{
tab[hash[temp-1].hash1] = temp;
return 1;
}
if ( tab[hash[temp-1].hash2] == 0 )
{
tab[hash[temp-1].hash2] = temp;
return 1;
}

//选择和slot不一样的单元递归下一个处理
if ( slot == hash[temp-1].hash1 )
{
//和初始的情况相同则返回0，发现循环
if ( hash[temp-1].hash2 == x && temp == y )
return 0;
//否则递归下一个处理过程
else
return solve ( hash[temp-1].hash2, temp );
}
else
{
if ( hash[temp-1].hash1 == x && temp == y )
return 0;
else
return solve ( hash[temp-1].hash1, temp );
}
}

int main ()
{
int t, i, j, m, n;

scanf ( "%d", &t );

for ( i = 0; i < t; i ++ )
{
scanf ( "%d%d", &m, &n );

for ( j = 0; j < m; j ++ )
scanf ( "%d%d", &hash[j].hash1, &hash[j].hash2) ;

memset ( tab, 0, sizeof ( int ) * m );

for ( j = 0; j < m; j++ )
{
//如果没有可放入，则直接放入并处理下一个
if ( tab[hash[j].hash1] == 0 )
{
tab[hash[j].hash1] = j + 1;

if ( j == m - 1 )
puts ( "successful hashing" );
continue;
}
if ( tab[hash[j].hash2] == 0 )
{
tab[hash[j].hash2] = j + 1;

if ( j == m - 1 )
puts ( "successful hashing" );
continue;
}

x= hash[j].hash1;
y = j + 1;

if ( solve ( hash[j].hash1, j + 1 ) )
{
if ( j == m - 1 )
puts ( "successful hashing" );
}
else
{
puts ( "rehash necessary" );
break;
}
}
}

return 0;
}

```

Followed by: