if you can help me,please...!
Code: Select all
#include <stdio.h>
#define offset 64
int main()
{
char graph[27][27] = {0};
int exist[27] = {0};
int count = 0;
char *last = "";
char *current = new char[21];
int flag = 0;
while(gets(current),current[0] != '#')
{
int k = 0;
while(current[k])
{
if(!exist[current[k] - offset])
exist[current[k] - offset] = 1;
k++;
}
k = 0;
while(last[k] && current[k])
{
if(last[k] != current[k])
{
count = graph[last[k] - offset][0];
flag = 0;
for(int i = 1;i<= count;i++)
if(graph[last[k] - offset][i] == current[k])
{
flag = 1;
break;
}
if(!flag)
{
graph[last[k] - offset][0]++;
graph[last[k] - offset][graph[last[k] - offset][0]] = current[k];
}
break;
}
else
k++;
}
last = current;
current = new char[21];
}
//DFS and TOPOLOGICAL SORT
int f[27] = {0};
int d[27] = {0};
int color[27] = {0};
int stack[27] = {0};
int counter[27];
for(int i = 1;i<= 26;i++)
counter[i] = 1;
int sPoint = 0;
int time = 0;
int k;
for(int i = 1;i <= 26;i++)
{
if(exist[i] == 1)
{
k = i;
if(color[k] == 0)
{
do{
if(color[k] == 0)
{
color[k] = 1;
time++;
d[k] = time;
stack[sPoint] = k;
sPoint++;
}
if(counter[k] <= graph[k][0] && color[graph[k][counter[k]] - offset] == 0)
{
counter[k]++;
k = graph[k][counter[k]-1] - offset;
}
else if(sPoint)
{
sPoint--;
k = stack[sPoint];
color[k] = 2;
time++;
f[k] = time;
}
}while(sPoint);
}
}
}
k = 0;
int result[27];
char letter[27];
for(int i = 1;i <= 26;i++)
{
if(exist[i] == 1)
{
result[k] = f[i];
letter[k] = i + offset;
k++;
}
}
int max = 0;
int maxindex;
for(int i = 0;i<=k-2; i++)
{
max = result[i];
maxindex = i;
for(int j = i+1;j<=k-1;j++)
{
if(result[j] > max)
{
max = result[j];
maxindex = j;
}
}
char temp = letter[maxindex];
letter[maxindex] = letter[i];
letter[i] = temp;
result[maxindex] = result[i];
result[i] = max;
}
for(int i = 0;i<=k-1;i++)
printf("%c",letter[i]);
printf("\n");
return 0;
}