Code: Select all
input:
====
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
0
Moderator: Board moderators
Code: Select all
input:
====
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
0
Code: Select all
Q.push(s);
while(!Q.empty()){
cur=Q.front();
Q.pop();
for(i=1;i<=n;i++){
if(node[cur][i]&&(cost[cur]+1)>cost[i]){
cost[i]=cost[cur]+1;
Q.push(i);
}
}
}
Code: Select all
while(true) {
scanf("%d%d",&a,&b);
if(a==0 && b==0) break;
node[a].edge[node[a].nedge++]=b;
}
Code: Select all
#include <cstdio>
bool adj[101][101] = {false};
// adj[i][j] : Are I and J connected?
int indegree[101];
int d[101];
int n; // n : The number of Vertexes
int end;
int result = 0;
int main()
{
int i, j;
int Case = 1;
while(true) {
scanf("%d", &n);
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) adj[i][j] = false;
indegree[i] = 0;
d[i] = 0;
}
if(n == 0) break;
int s; // s : starting vertex
scanf("%d", &s);
while(true) {
int p, q;
scanf("%d %d", &p, &q);
if(p == 0 && q == 0) break;
adj[p][q] = true;
++indegree[q];
}
// Starting Sort from vertex that we inputed
for(i = 1; i <= n; i++) {
if(!indegree[i] && i != s) {
indegree[i] = 0x7FFFFFFF;
}
}
indegree[s] = 0;
int v = 0;
while(v < n) { // Topological Sort
bool ended = false;
for(i = 1; i <= n; i++) {
if(!indegree[i]) {
++v;
for(j = 1; j <= n; j++) {
if(adj[j][i]) { // Get the distance of the Longest Path
if(d[j] + 1 > d[i]) d[i] = d[j] + 1;
}
if(adj[i][j]) {
--indegree[j];
--indegree[i];
}
}
if(d[i] > result) {
result = d[i];
end = i;
}
}
}
}
for(j = 1; j <= n; j++) {
if(!indegree[i]) break;
}
printf("Case%d: The longest path from %d", Case++, s);
printf(" has length %d, finishing at %d.\n\n", result, end);
}
return 0;
}
Code: Select all
#include<iostream>
using namespace std;
int main(){
class AdjListNode{
public:
AdjListNode *next;
int vert;
AdjListNode(int v, AdjListNode *ne){
vert = v;
next = ne;
}
};
int n, start, end, cnt, largest, v1, v2, front, rear, update;
int m = 1;
bool inside;
AdjListNode *Queue[200];
AdjListNode *Adj[200];
AdjListNode *link, *chase;
cin>>n;
while(n!=0){
for(int i=0; i<101; i++){
Adj[i] = NULL;
}
cnt = 1;
largest = -1;
front = rear = -1;
cin>>start; //starting point
cin>>v1>>v2;
while(v1!=0 && v2!=0){
Adj[v1] = new AdjListNode(v2, Adj[v1]);
cin>>v1>>v2;
}
link = Adj[start];
while(link != NULL){
inside = false;
chase = link;
while(Adj[chase->vert]!=NULL){
inside = true;
if(Adj[chase->vert]->next!=NULL){
Queue[++rear] = chase; //There are more than 1 things in the list, so queue it so you can go back and chase
Adj[chase->vert] = Adj[chase->vert]->next;
update = cnt; //save counter so you can go back
}
chase = Adj[chase->vert];
cnt++;
if(Adj[chase->vert]==NULL){
if(cnt>largest){
largest = cnt;
end = chase->vert;
}else if(cnt==largest){
if(chase->vert < end)
end = chase->vert;
}
if(front<rear){
if(front!=-1 && rear!=-1){
chase = Queue[++front];
cnt = update;
}
}
}
}
if(!inside){
if(cnt>largest){
largest = cnt;
end = chase->vert;
}else if(cnt==largest){
if(chase->vert < end)
end = chase->vert;
}
}
if(link->next!=NULL){
cnt = 1;
link = link->next;
}else break;
}
cout<<"Case "<<m<<": The longest path from "<<start<<" has length "<<largest<<", finishing at "<<end<<"."<<endl;
m++;
cin>>n;
}
}
Code: Select all
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 4
5 3
5 2
5 1
4 1
4 2
0 0
8
1
7 1
8 1
1 3
2 3
4 3
3 5
6 2
0 0
6
1
1 2
1 5
2 3
3 4
4 5
5 6
0 0
2
1
1 2
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.
Case 4: The longest path from 1 has length 2, finishing at 5.
Case 5: The longest path from 1 has length 5, finishing at 6.
Case 6: The longest path from 1 has length 1, finishing at 2.
Code: Select all
#include <iostream>
#include <string.h>
#include <list>
using namespace std;
#ifndef ONLINE_JUDGE
#include <fstream>
#define cin in
ifstream in("10000.in");
#endif
#define max(a,b) (a>b)? a : b
struct Node{
list<int> adj;
}Graph_B[100];
bool visited[100];
short wentTo[100];
short nNodes;
int LongestPath(short source)
{
if(visited[source])
return 0;
visited[source] = true;
int path = 0;
for(list<int>::iterator iter= Graph_B[source].adj.begin();
iter != Graph_B[source].adj.end(); iter++)
{
int i = (*iter);
int next = LongestPath(i)+1;
if(next > path) wentTo[source] = i;
path = max(path, next);
}
visited[source] = false;
return path;
}
void main()
{
cin >> nNodes;
int Case = 1;
while(nNodes != 0)
{
for(int i=0; i<nNodes; i++)
Graph_B[i].adj.clear();
memset(visited, 0, nNodes);
memset(wentTo, 0xFF, nNodes*2);
short Source;
cin >> Source;
Source--;
int from, to;
cin >> from >> to;
while( from != 0 || to != 0)
{
Graph_B[from-1].adj.push_back( to-1 );
cin >> from >> to;
}
cout << "Case " << Case++ << ": ";
cout << "The longest path from " << Source+1 << " has length " << LongestPath(Source);
int finish = Source;
while( wentTo[finish] != -1 ) finish = wentTo[finish];
cout << ", finishing at " << finish+1 << ".\n";
cin >> nNodes;
}
}
I think there are better ways to solve this problem.Biks wrote:i solved this problem using backtrack
but i am getting WA
Can anyone give me some critical test case so i can check wheres wrong
Code: Select all
#include<stdio.h>
#include<string.h>
#define N 110
struct g{
int node;
int status;
int len;
int num_edge;
int edge[N];
}graph[N];
int stck[N];
int top;
void push(int n)
{
stck[top]=n;
top++;
}
int pop()
{
int n;
top--;
n = stck[top];
return n;
}
void dfs(int n)
{
int i,j,k,l;
//int count;
//count = 0;
push(n);
graph[n].status = 2;
while(top)
{
i = pop();
graph[i].status = 3;
j = graph[i].num_edge;
for(k=0;k<j;k++)
{
l = graph[i].edge[k];
//graph[l].len++;
if(graph[i].len+1>graph[l].len)
graph[l].len = graph[i].len+1;
if( (graph[l].status == 1) )
{
push(l);
graph[l].status = 2;
}
}
}
// printf("%d\n",count);
}
int main()
{
int i;
int node;
int p,q;
int n;
int cases;
cases=0;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(i=1;i<=n;i++)
{
graph[i].node=i;
graph[i].status = 1;
graph[i].num_edge=0;
graph[i].len = 0;
memset(graph[i].edge,0,sizeof(graph[i].edge));
}
memset(stck,0,sizeof(stck));
top=0;
scanf("%d",&node);
while(1)
{
scanf("%d%d",&p,&q);
if(p==0 && q==0)
break;
i = graph[p].num_edge++;
graph[p].edge[i]=q;
}
dfs(node);
int max, end;
max = 0;
for(i=1;i<=n;i++)
{
if(max<graph[i].len)
{
max = graph[i].len;
end = i;
}
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",cases+1,node,max,end);
printf("\n");
cases++;
}
return 0;
}
Thanks in advance
5
5
3 4
1 2
0 0
Code: Select all
#include<stdio.h>
#include<string.h>
#define N 110
struct g{
int node;
int status;
int len;
int num_edge;
int edge[N];
}graph[N];
int stck[N];
int top;
void push(int n)
{
stck[top]=n;
top++;
}
int pop()
{
int n;
top--;
n = stck[top];
return n;
}
void dfs(int n)
{
int i,j,k,l;
//int count;
//count = 0;
push(n);
graph[n].status = 2;
while(top)
{
i = pop();
graph[i].status = 3;
j = graph[i].num_edge;
for(k=0;k<j;k++)
{
l = graph[i].edge[k];
//graph[l].len++;
if(graph[i].len+1>graph[l].len)
graph[l].len = graph[i].len+1;
if( (graph[l].status == 1) )
{
push(l);
graph[l].status = 2;
}
}
}
// printf("%d\n",count);
}
int main()
{
int i;
int node;
int p,q;
int n;
int cases;
cases=0;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(i=1;i<=n;i++)
{
graph[i].node=i;
graph[i].status = 1;
graph[i].num_edge=0;
graph[i].len = 0;
memset(graph[i].edge,0,sizeof(graph[i].edge));
}
memset(stck,0,sizeof(stck));
top=0;
scanf("%d",&node);
while(1)
{
scanf("%d%d",&p,&q);
if(p==0 && q==0)
break;
i = graph[p].num_edge++;
graph[p].edge[i]=q;
}
dfs(node);
int max, end;
max = 0;
for(i=1;i<=n;i++)
{
if(max<graph[i].len)
{
max = graph[i].len;
end = i;
}
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n",cases+1,node,max,end);
printf("\n");
cases++;
}
return 0;
}
5
5
3 4
1 2
0 0
About your input I dont think there is any such input in the judge data .. though the logical ans should be (0,5) but my AC code does not pass that as well ..5 1
1 2
2 3
3 4
1 3
4 5
0 0