10000 - Longest Paths

[brianfry713]

try using the Floyd Warshall algorithm.

[maddi]

Code: Select all

#include<stdio.h>

typedef struct listing{
int length,finishing_point,index;
};
int main()
{int cases[100][3];
int start,total_node,n;
n=0;
do{
scanf("%d",&total_node);
if(total_node==0)break;
scanf("%d",&start);
int a[100][total_node];
int p,q,i;
i=0;
do
{scanf("%d %d",&p,&q);
    a[i][0]=p;
    a[i][1]=q;
    i++;
}
while(p!=0||q!=0);
int j=i,k,l,m;
listing found[j-1];
m=0;
for(i=0;i<j-1;i++)
{if(start==a[i][0])
{k=1;
for(l=0;l<j-1;l++)
{
    if(a[i][k]==a[l][0])
    {  a[i][k+1]=a[l][1];
        k++;
    }
    if(k==total_node-1)break;
}
found[m].index=i;
found[m].length=k;
found[m].finishing_point=a[i][k];
m++;
}
}
int max_length=found[0].length,selected;
for(i=0;i<m;i++)
{if(found[i].length>max_length)
{max_length=found[i].length;
selected=i;
}
else if(found[i].length==max_length)
{
    for(j=1;j<max_length;j++)
    {if(a[found[selected].index][j]<a[found[i].index][j])
          break;
        else if(a[found[i].index][j]<a[found[selected].index][j])
        {selected=i;break;
        }

    }

}
}
if(m!=1)
{
cases[n][0]=start;
cases[n][1]=found[selected].length;
cases[n][2]=found[selected].finishing_point;
}
else{
cases[n][0]=start;
cases[n][1]=found[0].length;
cases[n][2]=found[0].finishing_point;
}
n++;
}
 while(total_node!=0);
 int i;
for(i=0;i<n;i++)
printf("Case %d: The longest path from %d has length %d , finishing at %d.\n",i+1,cases[i][0],cases[i][1],cases[i][2]);
    return 0;
}

[brianfry713]

Print a new line after each test case. You're also printing an extra space after the length.

[TryCatchMe]

I solved this in 0.065s using BFS in C. Consider this test case...

Code: Select all

4
1
1 3
1 2
2 3
1 2
0 0
0

ACC output is:

Code: Select all

Case 1: The longest path from 1 has length 3, finishing at 2.

The problem people are having with BFS is most likely due to not revisiting nodes. Although in a BFS you don't visit a node that has already been visited, in this problem it is possible to visit a node later on... when the path is longer! Use the test case above and let your BFS algorithm re-visit visited nodes if and only if a larger path was found. And with BFS you don't waste any time on the components that are not connected to the start vertex, like you would using Floyd-Warshall. And another thing, on this problem you WILL get WA if you do not put 2 newlines on every output line. I know some problems you cannot have any newlines at the end but you definitely need them for this one.

[LazyTym]

why WA?? can anyone see my code and give some advise???

Code: Select all

#include<iostream>
#include<vector>
#define MAX 101

using namespace std;
vector<vector<int> >g(MAX);
int dis[MAX];

void DFS_VISIT(int c,int visited[]) {
    int v;

    for(int i=0;i<g[c].size();i++) {

       v=g[c][i];
       dis[v]=dis[c]+1;
       if(visited[v]==0){
            visited[v]=1;
            DFS_VISIT(v,visited);
       }
    }
}


int DFS(int s,int n) {
    int v,maximum=0,finalPoint,visited[101];

    for(int i=0;i<101;i++) {
        dis[i]=0;
        visited[i]=0;
    }
    if(g[s].size()==0) return s;

    for(int i=0;i<g[s].size();i++) {
        v=g[s][i];
        dis[v]=1;
        visited[v]=1;
        DFS_VISIT(v,visited);
    }
     for(int i=1;i<=n;i++) {
        if(maximum<dis[i]) {
            maximum=dis[i];
            finalPoint=i;
        }
     }
     return finalPoint;
}



int main()
{
   

    int num_vertex,start,x,y,t=1,p;
    while(1) {
        cin>>num_vertex;
        if(num_vertex==0) break;
        cin>>start;
        for(int i=0;i<101;i++) g[i].clear();
        while(1) {
             cin>>x>>y;
             if(x==0 && y==0) break;
             g[x].push_back(y);
       }
       p=DFS(start,num_vertex);
       cout<<"Case "<<t<<": The longest path from "<<start<<" has length "<<dis[p]<<", finishing at "<<p<<"."<<endl<<endl;
       t++;
    }
    return 0;
}

thanks in advance

[brianfry713]

Don't read from a file.

[LazyTym]

Don't read from a file.

i do not read from a file now bt still i am getting WA...........check my code pls...i cann't find bug in my code........

[brianfry713]

Input:

Code: Select all

17
1
1 7
1 9
1 12
1 13
1 14
1 15
2 3
2 4
2 5
2 7
2 9
2 11
2 12
2 14
2 15
2 17
3 4
3 6
3 8
3 9
3 12
3 16
3 17
4 5
4 6
4 9
4 11
4 12
4 14
4 15
4 16
5 11
5 12
6 7
6 12
6 13
6 14
6 16
7 13
7 16
8 10
8 12
8 13
8 15
8 16
9 11
9 12
9 14
9 15
10 13
10 14
10 16
10 17
11 12
11 13
11 15
11 16
11 17
12 13
12 15
12 17
13 16
13 17
14 15
14 16
15 17
16 17
0 0
7
1
1 2
1 3
1 4
1 5
2 5
2 6
2 7
3 4
3 6
3 7
4 5
4 6
5 6
0 0
7
1
1 2
1 3
1 4
1 7
2 4
2 6
2 7
3 4
3 5
3 6
4 5
4 6
4 7
5 7
6 7
0 0
19
1
1 4
1 5
1 7
1 8
1 10
1 11
1 12
1 14
1 15
1 16
1 17
1 18
1 19
2 3
2 7
2 9
2 10
2 12
2 14
2 15
2 17
2 19
3 4
3 5
3 7
3 9
3 12
3 14
3 16
3 18
3 19
4 5
4 6
4 8
4 10
4 11
4 12
4 13
4 16
4 17
4 18
5 8
5 9
5 10
5 13
5 14
5 16
5 18
5 19
6 7
6 10
6 13
6 15
6 16
6 17
6 19
7 8
7 9
7 11
7 13
7 15
7 17
7 18
7 19
8 10
8 18
8 19
9 12
9 14
9 17
9 18
9 19
10 11
10 12
10 13
10 15
10 16
11 13
11 16
11 19
12 13
12 14
12 17
12 18
12 19
13 14
13 16
13 17
13 18
13 19
14 15
14 16
14 19
15 16
15 17
16 19
0 0
9
1
1 2
1 4
1 7
1 8
1 9
2 4
2 8
2 9
3 4
3 6
4 5
4 8
5 6
5 7
6 8
7 8
7 9
0 0
5
1
1 2
1 4
2 4
3 4
0 0
17
1
1 2
1 6
1 9
2 4
2 6
2 13
2 16
3 5
3 11
4 9
4 10
4 12
4 14
5 8
5 16
6 8
6 13
6 15
6 16
6 17
7 9
7 10
7 13
7 16
7 17
8 9
8 10
8 11
8 12
8 13
8 16
8 17
9 11
9 14
10 11
10 12
10 13
10 16
10 17
11 13
11 15
11 17
12 14
12 16
12 17
13 14
13 15
13 16
14 16
14 17
15 16
15 17
16 17
0 0
17
1
1 2
1 3
1 5
1 6
1 7
1 8
1 11
1 12
1 13
1 15
2 3
2 4
2 8
2 9
2 10
2 14
2 15
2 16
3 5
3 6
3 7
3 14
3 15
3 17
4 6
4 8
4 9
4 11
4 13
4 16
4 17
5 6
5 11
5 12
5 14
5 15
5 17
6 7
6 9
6 10
6 11
6 13
6 17
7 9
7 10
7 11
7 15
7 16
8 9
8 10
8 12
8 16
8 17
9 11
9 12
9 13
9 16
9 17
10 12
10 13
10 14
10 15
10 17
11 14
11 16
12 14
13 15
14 17
15 16
15 17
16 17
0 0
11
1
1 5
1 6
1 9
1 10
2 6
2 11
3 5
3 7
3 8
3 10
4 5
4 6
4 7
4 8
4 9
4 10
5 6
5 9
5 10
5 11
6 8
6 9
6 11
7 8
7 9
7 10
8 11
9 11
0 0
13
1
1 4
1 5
1 6
1 7
1 8
1 10
1 13
2 3
2 4
2 6
2 7
2 8
2 12
2 13
3 5
3 6
3 7
3 8
3 10
3 11
3 12
3 13
4 8
4 9
4 12
5 6
5 7
5 9
5 11
6 7
6 8
6 9
6 11
7 8
7 9
7 13
8 10
9 10
9 11
9 12
9 13
10 11
11 12
0 0
7
1
1 3
1 4
1 5
2 3
2 4
3 6
5 6
6 7
0 0
20
1
1 2
1 4
1 7
1 9
1 10
1 13
1 16
1 17
1 18
1 19
1 20
2 4
2 5
2 6
2 7
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 18
2 20
3 4
3 5
3 6
3 7
3 8
3 10
3 11
3 12
3 14
3 16
3 17
3 18
3 19
4 5
4 6
4 7
4 11
4 12
4 13
4 14
4 15
4 17
4 18
4 19
5 7
5 8
5 12
5 13
5 14
5 15
5 19
6 7
6 9
6 13
6 14
6 15
6 17
6 19
7 8
7 9
7 14
7 15
7 16
8 9
8 12
8 15
8 17
8 18
8 19
9 12
9 14
9 15
9 17
9 18
9 20
10 11
10 12
10 15
10 16
10 20
11 13
11 14
11 17
11 18
11 19
12 16
12 19
13 14
13 16
13 20
14 18
15 18
15 19
16 20
17 20
18 19
18 20
0 0
14
1
1 5
1 6
1 8
1 10
1 11
1 13
2 4
2 7
2 8
2 10
2 11
3 6
3 13
4 11
4 14
5 6
5 11
5 13
5 14
6 8
6 9
6 10
6 11
6 12
6 13
7 9
7 10
7 12
8 9
8 12
9 11
10 12
10 14
11 14
12 14
0 0
19
1
1 4
1 5
1 7
1 10
1 13
1 14
1 16
1 17
1 19
2 3
2 8
2 13
2 14
2 16
2 17
2 18
3 4
3 5
3 7
3 10
3 12
3 14
3 17
3 18
4 5
4 6
4 11
4 13
4 17
5 6
5 7
5 10
5 11
5 13
5 16
5 17
6 9
6 12
6 17
6 19
7 8
7 10
7 11
7 12
7 14
7 15
7 16
7 18
7 19
8 9
8 10
8 13
8 16
8 17
8 19
9 12
9 13
9 14
9 16
9 18
9 19
10 11
10 14
10 19
11 12
11 13
11 14
11 15
11 16
11 18
12 16
12 17
12 18
12 19
13 16
13 17
13 19
14 15
14 16
14 17
14 18
15 16
15 17
16 17
16 19
17 19
18 19
0 0
18
1
1 2
1 3
1 5
1 6
1 10
1 16
1 17
1 18
2 3
2 5
2 10
2 13
2 14
2 15
2 16
3 6
3 10
3 11
3 13
3 14
3 15
3 16
4 11
4 12
4 14
4 16
5 10
5 13
5 14
5 15
6 7
6 8
6 10
6 11
6 12
6 13
6 15
6 16
6 17
6 18
7 8
7 10
7 11
7 13
7 14
7 16
7 17
7 18
8 9
8 10
8 11
8 13
8 14
8 15
8 16
9 11
9 13
9 14
9 18
10 11
10 13
10 14
10 15
10 16
11 12
11 14
11 16
11 18
12 14
12 16
12 17
13 14
13 15
13 17
14 15
14 16
14 18
15 18
16 17
16 18
0 0
5
1
1 2
1 4
1 5
2 3
2 5
3 5
4 5
0 0
5
1
2 3
2 4
3 4
3 5
4 5
0 0
6
1
1 3
1 4
2 4
2 5
2 6
3 5
4 6
0 0
4
1
1 2
0 0
11
1
1 3
1 5
1 9
1 11
2 7
2 8
2 9
2 10
3 5
3 6
4 5
4 9
5 10
6 8
7 8
7 9
7 10
7 11
8 9
8 10
9 10
10 11
0 0
19
1
1 3
1 5
1 10
1 13
1 18
2 4
2 6
2 7
2 8
2 9
2 11
2 15
2 16
3 8
3 11
3 14
3 15
3 17
3 18
3 19
4 5
4 6
4 10
4 13
4 15
4 18
5 10
5 12
5 14
5 15
5 16
5 18
5 19
6 7
6 8
6 11
6 12
6 15
6 18
7 10
7 11
7 13
7 14
7 15
7 16
7 19
8 9
8 10
8 11
8 12
8 13
8 18
8 19
9 10
9 11
10 11
10 12
10 14
10 15
10 16
10 18
10 19
11 12
11 14
11 16
11 19
12 14
12 16
12 19
13 14
13 16
13 17
14 15
14 16
14 17
14 18
15 17
15 19
16 19
17 18
0 0
5
1
1 2
1 4
2 4
4 5
0 0
15
1
1 6
1 8
1 9
1 13
1 14
2 3
2 4
2 6
2 7
2 8
2 10
2 11
2 15
3 7
3 9
3 10
3 13
3 15
4 7
4 8
4 9
4 14
5 6
5 8
5 11
5 13
5 15
6 8
6 9
6 10
6 13
7 8
7 12
7 13
7 15
8 15
9 11
9 12
9 13
9 15
10 14
10 15
11 13
11 14
12 13
13 14
14 15
0 0
11
1
1 2
1 4
1 5
1 6
1 7
1 8
1 9
2 4
2 5
2 6
2 8
2 9
3 4
3 5
3 8
3 9
4 5
4 7
4 9
4 11
5 6
5 7
6 8
6 10
7 10
7 11
8 9
9 10
10 11
0 0
4
1
1 3
1 4
2 3
2 4
3 4
0 0
11
1
1 2
1 4
1 9
1 11
2 3
2 5
2 6
2 8
2 10
2 11
3 8
3 10
4 5
4 9
4 11
5 6
5 7
5 8
6 7
6 8
6 10
7 10
8 9
8 10
9 10
9 11
10 11
0 0
20
1
1 2
1 4
1 5
1 7
1 8
1 10
1 12
1 15
1 20
2 3
2 4
2 5
2 7
2 9
2 10
2 12
2 13
2 16
2 17
2 18
2 19
2 20
3 5
3 7
3 8
3 10
3 12
3 13
3 14
3 15
3 19
4 5
4 7
4 8
4 14
4 15
4 20
5 7
5 9
5 10
5 11
5 15
5 16
6 7
6 9
6 16
6 19
7 8
7 9
7 10
7 12
7 14
7 19
7 20
8 10
8 11
8 13
8 16
8 20
9 11
9 12
9 13
9 14
9 15
9 20
10 18
10 19
10 20
11 13
11 16
11 18
11 19
12 15
12 16
12 17
12 20
13 15
13 16
13 18
13 19
14 16
14 20
15 16
15 17
15 18
15 20
18 19
18 20
19 20
0 0
15
1
1 5
1 6
1 9
1 13
1 15
2 6
2 8
3 4
3 6
3 7
3 9
3 11
3 14
3 15
4 5
4 10
4 13
5 12
5 15
6 7
6 8
6 9
6 11
6 15
7 9
7 10
7 12
7 14
7 15
8 11
8 12
8 14
8 15
9 10
9 11
9 14
10 11
10 13
11 12
11 14
11 15
12 13
12 14
13 14
13 15
14 15
0 0
20
1
1 4
1 9
1 11
1 12
1 14
1 18
1 19
2 3
2 7
2 9
2 10
2 11
2 16
2 17
2 19
3 4
3 8
3 14
3 15
3 16
3 19
3 20
4 5
4 6
4 8
4 10
4 11
4 13
4 17
4 19
5 7
5 8
5 10
5 11
5 15
5 16
5 17
5 18
6 7
6 12
6 13
6 14
6 15
6 17
6 18
6 19
6 20
7 9
7 10
7 11
7 12
7 13
7 14
7 16
7 17
7 18
8 13
8 16
8 17
9 10
9 12
9 17
9 18
9 19
10 13
10 14
10 15
10 17
10 18
10 20
11 17
11 18
12 13
12 14
12 17
12 20
13 15
13 16
13 18
13 19
13 20
14 16
14 17
14 20
15 16
15 18
15 20
16 18
17 18
19 20
0 0
5
1
1 2
1 3
2 4
3 4
0 0
20
1
1 4
1 5
1 7
1 8
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 3
2 7
2 9
2 10
2 11
2 12
2 13
2 15
2 17
2 18
3 6
3 7
3 8
3 12
3 14
3 16
3 17
3 18
3 19
3 20
4 6
4 8
4 10
4 13
4 15
5 6
5 7
5 9
5 10
5 13
5 17
5 18
5 19
6 7
6 11
6 12
6 13
6 14
6 16
6 17
6 20
7 11
7 13
7 14
7 15
7 16
7 18
7 19
7 20
8 10
8 14
8 16
8 18
8 20
9 11
9 14
9 15
9 16
9 18
10 12
10 13
10 14
10 17
10 18
11 12
11 17
11 20
12 15
12 20
13 15
13 17
13 19
14 15
14 16
14 17
14 20
15 19
16 19
17 19
18 19
18 20
19 20
0 0
18
1
1 2
1 5
1 7
1 8
1 10
1 12
1 14
1 17
2 7
2 8
2 9
2 10
2 12
2 16
2 17
2 18
3 4
3 6
3 8
3 9
3 12
3 14
3 15
3 18
4 6
4 7
4 8
4 10
4 12
4 13
4 14
4 15
4 16
5 6
5 7
5 9
5 12
5 15
5 16
5 17
6 8
6 10
6 12
6 14
6 15
6 16
6 17
7 8
7 10
7 14
7 15
7 17
8 12
8 13
8 14
8 16
8 17
8 18
9 10
9 12
9 13
9 18
10 11
10 12
10 15
10 18
11 16
12 14
12 15
13 14
13 15
13 17
14 16
14 17
15 16
15 18
16 17
17 18
0 0
7
1
1 2
1 4
1 5
1 7
2 5
2 7
3 6
5 6
5 7
6 7
0 0
8
1
1 3
1 4
1 6
2 5
2 7
2 8
3 5
3 6
4 6
4 7
5 7
7 8
0 0
5
1
1 2
1 4
2 3
2 4
2 5
4 5
0 0
9
1
1 2
1 3
1 4
1 6
1 9
2 3
2 9
3 4
3 5
3 6
4 7
4 9
5 8
6 8
6 9
7 8
7 9
8 9
0 0
9
1
1 2
1 4
1 5
1 6
1 7
1 9
2 4
2 7
2 8
3 5
3 6
4 9
5 6
5 7
6 7
6 9
7 9
0 0
8
1
1 2
1 3
2 3
4 6
4 7
4 8
5 8
6 8
7 8
0 0
6
1
1 2
1 3
1 4
1 6
2 3
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
0 0
20
1
1 2
1 3
1 5
1 6
1 8
1 9
1 11
1 15
1 16
1 17
1 20
2 3
2 7
2 8
2 10
2 11
2 12
2 14
2 15
2 17
2 19
2 20
3 4
3 6
3 9
3 12
3 13
3 15
3 16
3 18
3 19
4 5
4 9
4 13
4 16
4 18
4 19
5 6
5 7
5 8
5 11
5 12
5 13
5 14
5 15
5 17
5 19
6 7
6 10
6 11
6 15
6 18
6 20
7 9
7 11
7 13
7 14
7 15
7 17
7 19
7 20
8 11
8 13
8 14
8 16
8 18
8 19
9 11
9 13
9 16
9 17
9 19
9 20
10 11
10 15
10 17
10 18
10 20
11 14
11 15
11 16
11 18
11 20
12 20
13 14
13 15
13 19
14 17
14 19
14 20
15 16
15 17
16 17
16 20
17 18
17 20
19 20
0 0
15
1
1 2
1 3
1 6
1 10
1 11
1 12
1 14
2 3
2 6
2 7
2 10
2 12
2 13
2 15
3 4
3 5
3 7
3 9
3 10
3 12
3 15
4 5
4 6
4 8
4 10
4 12
4 13
5 6
5 8
5 13
5 14
5 15
6 7
6 8
6 9
6 10
6 12
7 8
7 9
7 10
7 14
7 15
8 9
8 11
8 12
8 13
8 14
9 10
9 11
9 12
10 11
10 13
10 14
10 15
11 14
0 0
16
1
1 2
1 3
1 4
1 5
1 8
1 12
1 13
2 5
2 6
2 7
2 8
2 9
2 16
3 8
3 11
3 12
3 14
3 15
4 5
4 8
4 12
4 13
4 16
5 8
5 14
5 16
6 7
6 8
6 11
6 13
6 14
6 15
6 16
7 8
7 10
7 11
7 16
8 9
8 11
8 12
8 15
8 16
9 12
9 14
10 11
10 14
10 15
10 16
11 13
11 14
12 15
13 14
13 16
14 15
14 16
15 16
0 0
7
1
1 2
1 4
1 5
1 7
2 3
3 5
4 6
4 7
5 7
6 7
0 0
2
1
0 0
10
1
1 3
1 4
1 5
1 9
1 10
2 3
2 4
2 5
2 6
2 8
2 9
3 5
3 8
3 10
4 5
4 10
5 9
5 10
6 9
7 8
7 9
7 10
9 10
0 0
5
1
1 2
1 3
1 4
2 3
2 4
3 4
4 5
0 0
6
1
1 2
1 3
2 5
3 5
3 6
0 0
11
1
1 6
1 8
1 10
1 11
2 4
2 5
2 6
3 5
3 8
3 9
3 10
4 5
4 7
4 8
4 10
4 11
5 7
5 8
5 10
5 11
6 7
6 8
7 9
7 11
8 9
8 10
9 11
10 11
0 0
14
1
1 3
1 7
1 8
1 10
1 11
1 12
1 14
2 4
2 6
2 7
2 8
2 9
2 12
2 13
2 14
3 5
3 6
3 7
3 11
3 12
4 6
4 8
4 9
4 10
4 13
4 14
5 6
5 8
5 10
5 11
6 7
6 8
6 9
6 10
6 12
6 13
7 10
7 12
8 10
8 11
9 11
9 13
9 14
10 11
10 13
11 14
12 13
12 14
13 14
0 0
5
1
1 2
1 5
2 3
2 4
3 4
3 5
4 5
0 0
3
1
1 2
1 3
2 3
0 0
16
1
1 2
1 6
1 7
1 10
1 14
2 3
2 4
2 8
2 9
2 10
2 14
2 15
2 16
3 5
3 6
3 8
3 9
3 10
3 13
4 9
4 10
4 12
4 13
4 14
5 7
5 9
5 13
5 14
6 9
6 11
6 12
6 13
6 14
6 15
6 16
7 8
8 11
8 12
8 13
8 15
8 16
9 10
9 16
10 11
10 12
10 15
10 16
11 12
11 14
11 15
11 16
12 14
12 15
13 15
14 15
15 16
0 0
17
1
1 2
1 3
1 4
1 5
1 6
1 7
1 9
1 11
1 14
1 15
1 16
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 10
3 11
3 16
3 17
4 5
4 6
4 7
4 11
4 12
4 17
5 6
5 9
5 10
5 11
5 16
5 17
6 8
6 9
6 12
6 13
6 14
7 8
7 9
7 10
7 11
7 14
7 15
7 16
7 17
8 9
8 11
8 12
8 14
8 15
8 17
9 15
9 16
9 17
10 12
10 13
10 16
11 13
11 15
11 17
12 13
12 15
12 17
13 14
13 15
13 17
14 17
15 16
16 17
0 0
4
1
1 2
2 3
3 4
0 0
11
1
1 2
1 3
1 4
1 6
1 7
2 3
2 5
2 7
2 8
2 9
3 5
3 7
3 8
3 10
3 11
4 5
4 6
4 10
5 8
5 9
5 11
6 7
6 8
6 9
6 10
6 11
8 11
9 10
9 11
0 0
2
1
1 2
0 0
10
1
1 6
1 9
2 3
2 5
2 9
2 10
3 6
3 10
4 6
4 10
5 9
6 7
6 8
6 9
7 8
7 10
8 10
9 10
0 0
19
1
1 4
1 6
1 7
1 8
1 9
1 11
1 13
1 14
2 3
2 4
2 5
2 9
2 11
2 13
2 15
3 4
3 5
3 6
3 7
3 10
3 11
3 14
3 18
3 19
4 5
4 6
4 7
4 8
4 13
4 15
4 16
4 18
5 7
5 8
5 9
5 10
5 16
5 18
5 19
6 7
6 9
6 15
6 16
6 17
6 18
7 8
7 11
7 13
7 15
7 18
8 11
8 13
8 14
8 15
8 16
8 18
8 19
9 12
9 13
9 14
9 15
9 16
9 17
9 19
10 11
10 12
10 13
10 15
10 19
11 14
11 16
11 18
12 14
12 16
12 17
12 19
13 14
13 15
14 15
14 17
15 18
16 17
16 18
16 19
17 18
17 19
0 0
20
1
1 4
1 5
1 7
1 8
1 12
1 17
1 19
1 20
2 4
2 5
2 6
2 9
2 10
2 11
2 13
2 14
2 15
2 16
2 20
3 4
3 6
3 7
3 9
3 10
3 12
3 16
4 6
4 7
4 8
4 10
4 12
4 14
4 16
4 17
4 18
5 6
5 10
5 16
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
7 8
7 10
7 11
8 9
8 10
8 12
8 13
8 14
8 15
8 16
8 20
9 10
9 11
9 15
9 16
9 20
10 13
10 15
10 17
10 18
10 19
11 12
11 14
11 16
11 19
11 20
12 14
12 17
12 19
13 14
13 20
14 15
14 16
14 17
15 17
15 18
15 19
15 20
17 18
17 20
18 19
0 0
10
1
1 4
1 7
2 3
2 6
2 9
3 4
3 5
3 6
3 8
3 9
4 6
4 7
4 8
4 10
5 6
5 8
6 7
6 8
6 10
7 10
8 10
0 0
15
1
1 2
1 6
1 8
1 9
1 11
1 13
2 6
2 11
2 12
2 14
2 15
3 6
3 8
3 9
3 11
3 15
4 6
4 8
4 11
4 13
5 6
5 12
5 13
6 8
6 9
6 10
6 11
6 12
6 13
6 15
7 8
7 10
7 11
7 13
7 14
7 15
8 9
8 12
9 14
9 15
10 12
10 14
11 12
11 15
12 14
13 14
0 0
16
1
1 2
1 3
1 4
1 6
1 13
2 4
2 8
2 11
2 13
2 14
2 15
2 16
3 4
3 5
3 11
3 14
3 15
4 6
5 6
5 7
5 8
5 12
5 15
6 7
6 8
6 9
6 10
6 11
6 12
6 15
8 10
8 11
8 12
8 13
8 15
9 14
9 15
10 12
10 13
10 14
10 15
11 12
11 13
11 15
12 13
12 14
12 16
13 14
13 15
13 16
14 15
0 0
10
1
1 3
1 4
1 6
1 7
1 8
1 10
2 3
2 4
2 8
2 9
3 4
3 8
4 5
4 6
4 7
4 10
5 6
6 7
6 8
6 9
7 8
7 10
8 9
8 10
0 0
3
1
0 0
11
1
1 7
1 9
1 10
2 3
2 6
2 9
2 11
3 4
3 5
3 6
3 11
4 5
4 7
4 10
5 6
5 9
5 10
5 11
6 7
6 10
7 9
7 10
8 11
9 10
0 0
5
1
1 2
1 3
1 4
1 5
2 4
3 4
3 5
4 5
0 0
13
1
1 2
1 4
1 5
1 6
1 7
1 8
1 10
1 11
1 12
2 4
2 6
2 8
2 9
2 13
3 4
3 7
3 11
3 12
4 7
4 9
4 10
4 11
4 12
5 7
5 8
5 12
6 8
6 11
6 12
7 9
7 11
8 9
8 10
8 12
8 13
9 13
10 11
11 13
0 0
15
1
1 4
1 6
1 7
1 8
1 10
1 11
1 12
1 15
2 7
2 8
2 10
2 12
2 15
3 4
3 5
3 7
3 12
3 13
3 14
3 15
4 5
4 8
4 9
4 11
4 12
4 14
5 8
5 10
5 13
5 14
6 7
6 10
6 11
6 13
6 15
7 9
7 10
7 11
7 14
7 15
8 9
8 10
8 11
8 12
8 13
8 14
8 15
9 10
9 12
9 14
11 12
11 14
12 13
12 14
12 15
0 0
10
1
1 2
1 3
1 5
1 9
1 10
2 7
3 9
4 5
4 7
4 8
4 9
4 10
5 8
5 9
5 10
6 7
6 8
6 10
7 10
0 0
12
1
1 9
1 11
2 5
2 6
2 7
2 8
2 11
3 4
3 5
3 6
3 7
3 8
3 10
3 11
4 5
4 6
4 7
4 8
4 9
4 10
4 12
5 6
5 9
6 8
6 9
6 11
7 10
7 11
7 12
8 10
8 12
9 11
10 11
10 12
11 12
0 0
11
1
1 2
1 4
1 5
1 9
2 8
4 5
4 6
4 8
4 11
5 6
5 7
5 8
5 9
6 7
7 9
7 10
8 9
8 10
8 11
9 10
9 11
10 11
0 0
9
1
1 2
1 3
1 6
2 3
2 5
2 7
2 8
3 4
3 5
3 7
3 9
4 6
4 7
4 8
5 7
5 8
5 9
6 8
6 9
7 8
7 9
0 0
2
1
0 0
15
1
1 4
1 6
1 8
1 11
1 12
1 15
2 3
2 5
2 6
2 12
2 13
2 14
2 15
3 4
3 6
3 9
3 10
3 11
3 15
4 6
4 11
4 13
5 6
5 9
5 11
5 12
5 13
5 14
5 15
6 8
6 10
6 12
6 13
6 15
7 11
7 14
7 15
8 11
8 12
8 13
8 15
9 12
9 13
9 14
10 11
10 12
10 13
10 14
11 12
11 14
12 13
13 14
13 15
14 15
0 0
20
1
1 7
1 8
1 10
1 11
1 14
1 15
1 19
1 20
2 5
2 6
2 9
2 10
2 11
2 14
2 20
3 4
3 7
3 11
3 14
3 15
3 16
3 17
3 20
4 8
4 9
4 10
4 11
4 12
4 13
4 15
4 19
4 20
5 6
5 8
5 9
5 11
5 15
5 16
5 18
5 19
5 20
6 8
6 9
6 10
6 11
6 13
6 16
6 17
6 19
6 20
7 8
7 15
7 17
7 18
7 19
8 9
8 10
8 13
8 14
8 19
9 12
9 15
9 18
10 11
10 13
10 14
10 15
10 16
10 17
11 13
11 14
11 15
11 16
11 17
11 19
11 20
12 15
12 18
12 19
13 19
14 15
14 17
14 20
15 19
16 17
16 18
16 20
17 20
18 19
19 20
0 0
6
1
1 2
1 4
2 3
2 5
2 6
3 4
0 0
15
1
1 2
1 5
1 7
1 8
1 9
1 10
1 11
1 15
2 3
2 4
2 5
2 7
2 10
2 11
2 12
2 13
2 14
3 4
3 7
3 8
3 10
3 14
3 15
4 5
4 7
4 10
4 11
4 15
5 8
5 10
5 12
5 13
5 14
5 15
6 7
6 15
7 11
7 15
8 10
8 11
8 13
8 14
8 15
9 10
9 11
9 12
9 13
10 14
11 13
11 15
12 13
12 15
13 14
14 15
0 0
14
1
1 5
1 8
1 9
1 10
1 14
2 3
2 6
2 8
2 9
2 10
2 12
2 14
3 5
4 6
4 8
4 9
4 11
4 12
4 13
4 14
5 6
5 8
5 10
5 13
6 8
6 9
6 11
6 12
6 14
7 10
8 9
8 11
8 13
9 10
9 12
9 13
10 12
10 14
12 13
12 14
13 14
0 0
2
1
1 2
0 0
9
1
1 2
1 5
1 7
2 3
2 4
2 7
3 5
3 7
4 7
4 8
5 8
5 9
6 7
6 9
7 9
0 0
20
1
1 2
1 12
1 14
1 19
1 20
2 4
2 5
2 6
2 7
2 8
2 9
2 11
2 12
2 18
2 19
3 4
3 5
3 7
3 8
3 10
3 11
3 13
3 14
3 18
3 19
3 20
4 7
4 8
4 9
4 11
4 12
4 15
4 16
4 17
4 18
5 6
5 8
5 9
5 10
5 18
5 19
5 20
6 10
6 11
6 14
6 15
6 19
7 8
7 10
7 11
7 12
7 13
7 16
7 19
8 11
8 12
8 14
8 16
8 17
9 10
9 16
9 20
10 11
10 13
10 16
10 17
10 19
10 20
11 12
11 13
11 15
11 16
11 17
11 19
11 20
12 14
12 17
12 19
13 15
13 17
13 20
14 18
15 17
15 18
16 20
17 18
18 19
18 20
19 20
0 0
6
1
1 3
1 4
1 5
1 6
2 3
2 4
2 5
3 4
3 5
4 6
0 0
6
1
1 2
1 3
1 4
1 5
1 6
2 3
2 5
3 5
4 5
4 6
5 6
0 0
20
1
1 3
1 7
1 8
1 11
1 15
1 16
1 17
1 20
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 12
2 13
2 17
3 4
3 6
3 9
3 10
3 11
3 16
3 18
3 20
4 5
4 7
4 9
4 10
4 11
4 12
4 13
4 14
4 16
4 17
4 18
4 20
5 7
5 9
5 11
5 14
5 17
6 7
6 10
6 11
6 12
6 13
6 14
6 17
6 18
7 8
7 9
7 12
7 15
7 17
7 20
8 11
8 13
8 16
8 17
8 18
9 10
9 18
9 20
10 11
10 12
10 14
10 16
10 17
10 18
10 19
11 13
11 14
11 19
12 14
12 15
12 17
12 18
12 19
12 20
13 14
13 17
13 18
13 19
13 20
14 16
14 18
14 20
15 16
15 18
15 19
15 20
16 17
16 18
16 19
17 19
17 20
18 19
19 20
0 0
4
1
1 2
2 3
3 4
0 0
13
1
1 2
1 6
1 7
1 10
1 11
1 12
2 5
2 6
2 7
2 8
2 13
3 4
3 5
3 7
4 7
4 9
4 11
4 13
5 6
5 10
5 11
5 13
6 7
6 10
6 11
6 12
6 13
7 10
7 13
8 9
8 10
8 13
9 10
9 13
10 12
10 13
11 13
0 0
12
1
1 2
1 3
1 6
1 7
1 8
1 9
1 12
2 5
2 6
2 7
2 9
2 11
3 5
3 6
4 5
4 6
4 9
4 10
4 11
4 12
5 8
5 9
5 11
5 12
6 7
6 8
6 9
6 10
6 11
6 12
7 8
7 9
7 11
8 9
8 10
8 12
0 0
10
1
1 2
1 3
1 5
1 7
1 8
1 9
2 3
2 7
2 8
2 9
2 10
3 4
3 6
3 9
3 10
4 6
4 9
5 6
5 7
5 8
5 9
6 7
6 8
7 8
7 9
7 10
8 9
8 10
0 0
12
1
1 3
1 5
1 8
1 11
1 12
2 4
2 5
2 9
3 4
3 8
3 9
4 6
4 7
4 11
4 12
5 7
5 9
5 10
5 11
6 7
6 8
6 11
6 12
7 10
7 12
8 9
8 11
8 12
9 11
10 11
0 0
11
1
1 2
1 3
1 4
1 6
1 7
1 8
1 10
2 6
2 7
3 4
3 5
3 8
3 10
3 11
4 6
4 8
4 10
4 11
5 7
5 9
5 10
5 11
6 7
6 8
6 9
6 10
6 11
7 9
7 10
7 11
10 11
0 0
6
1
1 2
1 3
1 4
1 5
1 6
2 4
2 6
3 5
3 6
4 5
4 6
5 6
0 0
4
1
2 3
2 4
0 0
8
1
2 3
2 5
2 7
3 4
4 8
5 6
5 7
5 8
6 7
6 8
7 8
0 0
10
1
1 2
1 3
1 5
1 7
1 10
2 3
2 7
2 9
3 5
3 8
3 10
4 6
4 7
4 9
5 8
5 9
6 7
7 8
7 9
8 9
8 10
0 0
8
1
1 4
1 8
2 3
2 4
3 4
4 5
4 7
4 8
5 7
6 7
7 8
0 0
8
1
1 4
1 7
2 4
2 5
2 6
2 7
3 5
3 6
3 8
4 5
4 7
4 8
5 8
6 7
6 8
7 8
0 0
12
1
1 4
1 5
1 6
1 7
1 8
1 9
1 11
2 3
2 5
2 6
2 9
2 10
2 11
3 4
3 7
3 8
3 9
3 10
4 9
4 11
5 6
5 7
5 8
5 9
5 10
6 10
6 11
6 12
7 9
8 9
8 10
8 11
8 12
9 12
11 12
0 0
17
1
1 2
1 3
1 4
1 5
1 6
1 9
1 12
1 15
2 7
2 8
2 11
2 13
3 4
3 8
3 12
3 13
3 14
3 15
3 16
4 5
4 6
4 8
4 9
4 10
4 13
4 16
5 7
5 13
5 14
5 15
5 16
5 17
6 9
6 10
6 11
6 12
6 13
6 17
7 8
7 9
7 12
7 14
7 15
8 13
8 14
8 17
9 10
9 12
9 14
9 15
10 11
10 13
10 14
10 15
10 17
11 12
11 13
11 14
11 16
11 17
12 14
12 15
12 17
13 16
14 15
14 16
15 17
0 0
3
1
1 2
2 3
0 0
5
1
1 2
1 5
2 3
2 4
2 5
3 5
0 0
0

AC output:

Code: Select all

Case 1: The longest path from 1 has length 6, finishing at 17.

Case 2: The longest path from 1 has length 4, finishing at 6.

Case 3: The longest path from 1 has length 4, finishing at 7.

Case 4: The longest path from 1 has length 11, finishing at 19.

Case 5: The longest path from 1 has length 5, finishing at 8.

Case 6: The longest path from 1 has length 2, finishing at 4.

Case 7: The longest path from 1 has length 9, finishing at 17.

Case 8: The longest path from 1 has length 10, finishing at 17.

Case 9: The longest path from 1 has length 4, finishing at 11.

Case 10: The longest path from 1 has length 7, finishing at 12.

Case 11: The longest path from 1 has length 3, finishing at 7.

Case 12: The longest path from 1 has length 9, finishing at 19.

Case 13: The longest path from 1 has length 6, finishing at 14.

Case 14: The longest path from 1 has length 11, finishing at 19.

Case 15: The longest path from 1 has length 11, finishing at 17.

Case 16: The longest path from 1 has length 3, finishing at 5.

Case 17: The longest path from 1 has length 0, finishing at 1.

Case 18: The longest path from 1 has length 2, finishing at 5.

Case 19: The longest path from 1 has length 1, finishing at 2.

Case 20: The longest path from 1 has length 6, finishing at 11.

Case 21: The longest path from 1 has length 10, finishing at 18.

Case 22: The longest path from 1 has length 3, finishing at 5.

Case 23: The longest path from 1 has length 6, finishing at 15.

Case 24: The longest path from 1 has length 8, finishing at 11.

Case 25: The longest path from 1 has length 2, finishing at 4.

Case 26: The longest path from 1 has length 7, finishing at 11.

Case 27: The longest path from 1 has length 11, finishing at 20.

Case 28: The longest path from 1 has length 9, finishing at 15.

Case 29: The longest path from 1 has length 9, finishing at 18.

Case 30: The longest path from 1 has length 2, finishing at 4.

Case 31: The longest path from 1 has length 8, finishing at 20.

Case 32: The longest path from 1 has length 8, finishing at 18.

Case 33: The longest path from 1 has length 4, finishing at 7.

Case 34: The longest path from 1 has length 4, finishing at 8.

Case 35: The longest path from 1 has length 3, finishing at 5.

Case 36: The longest path from 1 has length 6, finishing at 9.

Case 37: The longest path from 1 has length 4, finishing at 9.

Case 38: The longest path from 1 has length 2, finishing at 3.

Case 39: The longest path from 1 has length 5, finishing at 6.

Case 40: The longest path from 1 has length 12, finishing at 18.

Case 41: The longest path from 1 has length 11, finishing at 14.

Case 42: The longest path from 1 has length 9, finishing at 16.

Case 43: The longest path from 1 has length 4, finishing at 7.

Case 44: The longest path from 1 has length 0, finishing at 1.

Case 45: The longest path from 1 has length 4, finishing at 10.

Case 46: The longest path from 1 has length 4, finishing at 5.

Case 47: The longest path from 1 has length 2, finishing at 5.

Case 48: The longest path from 1 has length 4, finishing at 11.

Case 49: The longest path from 1 has length 7, finishing at 14.

Case 50: The longest path from 1 has length 4, finishing at 5.

Case 51: The longest path from 1 has length 2, finishing at 3.

Case 52: The longest path from 1 has length 10, finishing at 16.

Case 53: The longest path from 1 has length 10, finishing at 17.

Case 54: The longest path from 1 has length 3, finishing at 4.

Case 55: The longest path from 1 has length 5, finishing at 10.

Case 56: The longest path from 1 has length 1, finishing at 2.

Case 57: The longest path from 1 has length 4, finishing at 10.

Case 58: The longest path from 1 has length 8, finishing at 18.

Case 59: The longest path from 1 has length 11, finishing at 19.

Case 60: The longest path from 1 has length 4, finishing at 10.

Case 61: The longest path from 1 has length 5, finishing at 14.

Case 62: The longest path from 1 has length 9, finishing at 15.

Case 63: The longest path from 1 has length 7, finishing at 9.

Case 64: The longest path from 1 has length 0, finishing at 1.

Case 65: The longest path from 1 has length 3, finishing at 10.

Case 66: The longest path from 1 has length 3, finishing at 5.

Case 67: The longest path from 1 has length 6, finishing at 13.

Case 68: The longest path from 1 has length 6, finishing at 13.

Case 69: The longest path from 1 has length 3, finishing at 10.

Case 70: The longest path from 1 has length 3, finishing at 12.

Case 71: The longest path from 1 has length 7, finishing at 11.

Case 72: The longest path from 1 has length 5, finishing at 8.

Case 73: The longest path from 1 has length 0, finishing at 1.

Case 74: The longest path from 1 has length 8, finishing at 15.

Case 75: The longest path from 1 has length 8, finishing at 20.

Case 76: The longest path from 1 has length 3, finishing at 4.

Case 77: The longest path from 1 has length 9, finishing at 15.

Case 78: The longest path from 1 has length 8, finishing at 14.

Case 79: The longest path from 1 has length 1, finishing at 2.

Case 80: The longest path from 1 has length 4, finishing at 8.

Case 81: The longest path from 1 has length 11, finishing at 20.

Case 82: The longest path from 1 has length 3, finishing at 6.

Case 83: The longest path from 1 has length 4, finishing at 6.

Case 84: The longest path from 1 has length 13, finishing at 20.

Case 85: The longest path from 1 has length 3, finishing at 4.

Case 86: The longest path from 1 has length 6, finishing at 12.

Case 87: The longest path from 1 has length 5, finishing at 9.

Case 88: The longest path from 1 has length 7, finishing at 9.

Case 89: The longest path from 1 has length 6, finishing at 11.

Case 90: The longest path from 1 has length 6, finishing at 11.

Case 91: The longest path from 1 has length 4, finishing at 6.

Case 92: The longest path from 1 has length 0, finishing at 1.

Case 93: The longest path from 1 has length 0, finishing at 1.

Case 94: The longest path from 1 has length 5, finishing at 9.

Case 95: The longest path from 1 has length 4, finishing at 8.

Case 96: The longest path from 1 has length 3, finishing at 8.

Case 97: The longest path from 1 has length 4, finishing at 12.

Case 98: The longest path from 1 has length 11, finishing at 17.

Case 99: The longest path from 1 has length 2, finishing at 3.

Case 100: The longest path from 1 has length 3, finishing at 5.

[AsmaeFILALI]

this code works well in Eclipse , i don't know why im getting Time limit exceeded , can anyone help ???

Code: Select all

import java.util.Scanner;
import java.util.LinkedHashMap;
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author info
 */
class Main {

    public static void main(String[] args) {
        Main mc = new Main();
        mc.begin();
    }

    void begin() {   //LinkedHashMap<Integer,Integer> lk;
        Scanner sc = new Scanner(System.in);
        int[][] tab;

        int pl, start, path, nextstep = 0, a, b, i, j, fin, temp;

        boolean next, nextp;
        int cases = 0;
        pl = sc.nextInt();
        while (pl != 0) {
            next = true;
            nextp = true;
            cases++;
            tab = new int[pl * pl][pl * pl];

            start = sc.nextInt();
            path = 0;
            i = 0;
            a = sc.nextInt();
            b = sc.nextInt();

            while (a > 0 && b > 0) {
                if (i > 0) {
                    a = sc.nextInt();
                    b = sc.nextInt();
                }

                tab[i][0] = a;
                tab[i][1] = b;

                
                i++;
              

            }
            i = 0;
            fin = 0;
            temp = 0;
            while (tab[i][0] != 0) {
                temp = 0;
                if (tab[i][0] == start) {
                    nextstep = tab[i][1];
                    next = true;
                    j = 0;
                    temp++;
                    while (tab[j][0] != 0) {
                        if (tab[j][0] == nextstep) {
                            nextstep = tab[j][1];
                            temp++;
                        }

                        j++;
                    }
                    if (path < temp) {
                        fin = nextstep;
                        path = temp;
                    }

                }

                i++;
            }
            System.out.println("\n Case " + cases + ": The longest path from " + start + " has length " + path + ", finishing at " + nextstep + ".");
            pl = sc.nextInt();
        }

    }
//    
}

thank you

[brianfry713]

Next time post in the existing thread.

Try using BufferedReader and BufferedWriter.

[jddantes]

Are test cases like this valid?

Code: Select all

4 
1
1 2
4 3
3 2
0 0
0

Shouldn't all nodes (including 4 and 3) be reachable from the starting node (1) ?