10000 - Longest Paths

[lky]

i use dfs to search......but time exceed.....is there a way to minimize time without rewriteing?

[sohel]

Yes there is.

First consider all the nodes that can be reached in one move.
And then nodes that can be reached in two moves - whose source is definitely nodes reachable in one move.

In this way keep increasing the length and find the answer.

[czar]

I was wondering if anyone could tell me what is wrong with my code or if I am even using the right algorithm.

I just topological sort the vertices.

[cpp]
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;

vector<vector<int> > g;
vector<int> indeg;
int maxl, minv;

vector<int> toposort(int start, int nv) {
int depth = -1;
int mv;
vector<int> ret(2);
queue<int> q;

q.push(start);

while(!q.empty()) {
int qs = q.size();
mv = INT_MAX;
++depth;

for(int i = 0; i < qs; i++) {
int next = q.front(); q.pop();
mv = min(mv, next);
vector<int>::iterator s = g[next].begin(), e = g[next].end();

//cout<<"NEXT: "<<next<<endl;

while(s != e) {
--indeg[*s];
if(!indeg[*s]) {
//cout<<" "<<*s<<endl;
q.push(*s);
}
++s;
}
//cout<<"DEPTH: "<<depth<<endl;
}
}
ret[0] = depth; ret[1]=mv;
return ret;
}

int main() {
int nv;
int start;
int i = 1;

while( cin>>nv ) {
cin.ignore();
if(nv == 0) break;

g = vector<vector<int> >(nv+1, vector<int>());
indeg = vector<int>(nv+1);
vector<int> ret;

int start;
int from, to;

cin>>start; cin.ignore();
cin>>from>>to; cin.ignore();

while(from != 0 || to != 0) {
g[from].push_back(to);
++indeg[to];
cin>>from>>to; cin.ignore();
}

ret = toposort(start, nv);
cout<<"Case "<<i<<":"<<" The longest path from "<<start<<" has length "<<ret[0]<<", finishing at "<<ret[1]<<".\n\n";
++i;
}
return 0;
}
[/cpp]

[Sajid]

I solved this problem using DFS long ago.
After the rejudgement, I got TLE.

Now, I used BFS to solve this problem. But its get RTE always. I increased the Queue size a lot. but still RTE. (Using Circuler Queue, I got WA).

What can I do now?

[Observer]

You don't need a long long queue here. Just... use a BIG boolean array (of size[1..100, 1..100]) to store visited states, thus you may avoid visiting the same state more than once. Think about it.

P.S. By "state" here I mean "visiting node I with distance J".

[Sajid]

I did so, but now gets WA...What is the problem now?

[sunhong]

I got several WA on this problem.
I use BFS to solve it. I don't know why. Please help me, thanks.
[cpp]void solve()
{int u,v,k;
queue.clear(); queue.push_back(s);
memset(visited,0,sizeof(visited)); visited[s]=1;
memset(dist,0,sizeof(dist));
while (!queue.empty())
{u=queue.front(); queue.pop_front();
for (k=0;k<adj.size();k++)
{v=adj[k];
dist[v]=dist+1;
if (maxd<dist[v] || (maxd==dist[v] && t>v)) {maxd=dist[v]; t=v;}
if (!visited[v]) {visited[v]=1; queue.push_back(v);}
}
}
}
int main()
{int i,j,count;
//freopen("data.in","r",stdin);
count=0;
while (scanf("%d",&n) && n!=0)
{scanf("%d",&s);
for (i=0;i<=n;i++) adj.clear();
scanf("%d %d",&i,&j);
while (!(i==0 && j==0))
{adj.push_back(j);
scanf("%d %d",&i,&j);
}
maxd=-1; t=10010;
solve();
printf("Case %d: The longest path from %d has length %d, finishing at %

d.\n\n",++count,s,maxd,t);
}
return 1;
} [/cpp]

[shamim]

I did not check your code throughly, but you could try something yourself.
With a little time-expense, the problem can be solved using Warshall's Algorithm. I was also getting WA with BFS, then i used Warshall and got AC.

You can test the output of the two programs for larger input to find if any difference occurs.

[abishek]

Even I use topological sorting. But I always get WA.
any thing wrong with the algo?
abi

[Larry]

I had used naive DFS the first time, but if you just keep track of "best" of each node, and only DFS when it's better, that's good enough for AC for me. (Simple pruning..)

[Dreamer#1]

hey per, thanks a lot man for such a quick response.

i made a really stupid mistake in my code for cycle checking.

hope not too many people got misguided in this short time. next time i will consult with 1 or 2 people before making any such conclusions.

and per, thanks again for such a quick response.



n.b. if any of you can't understand what i'm talking about then please skip my post and may be the per's one (next) too. i made a wrong statement and he pointed it out .

[Per]

I got AC using topological sort. I think the trouble with the new input is not that the graphs are cyclic, but that there are nodes which are not reachable from the starting node.

It would be very interesting if you could tell me how you solved the problem without assuming that the graph is acyclic: in general, that is an NP-complete problem.

[tlucz]

Hi! I got a WA on this problem, too. I think that my program works good. Could someone give me input and output sample??? That is my code:
[cpp]
#include <iostream>

using namespace std;

int ile_wezlow;
int poczatek;

int maks;
int przypadek;
int tabela[110][110];
int sumy[110];
int konce[110];
int najm[110];


void inicjalizacja() {
int i,j;
for(i=1;i<=ile_wezlow;i++)
for(j=1;j<=ile_wezlow;j++)
tabela[j]=0;

for(i=1;i<=ile_wezlow;i++) {
sumy=-1;
konce=1;
najm=200;

}
}


void wypisz() {

cout << "Case " << przypadek << ": The longest path from " << poczatek << " has length " << maks << ", finishing at " << najm[poczatek] << "." << endl << endl;
}




int licz(int numer) {
int i,ile,m,m1;
m=0;
m1=200;

if (sumy[numer]!=-1) {
return sumy[numer];
}
else {
for(i=1;i<=ile_wezlow;i++) {
if (tabela[numer]==1) {
ile=licz(i)+1;
if (ile>=m) {

if (ile>m) {
m1=najm;
m=ile;
}
else {
if (najm<m1) { m1=najm; }
}

}
}
}

sumy[numer]=m;
najm[numer]=m1;

return m;
}
}


void oblicz() {
int i;
for(i=1;i<=ile_wezlow;i++) {
if (konce==1)
{
sumy=0;
najm[i]=i;
}
}
maks=licz(poczatek);
}


int main(void){

int x,y;

przypadek=0;

while(1) {
cin >> ile_wezlow;
if (ile_wezlow==0) goto koniec;
inicjalizacja();
cin >> poczatek;
maks=0;
przypadek++;
while(1) {
cin >> x;
cin >> y;
if ((x==0) && (y==0)) goto oblicz;
if (x!=y) {
tabela[x][y]=1;
konce[x]=0;
}

}
oblicz:
oblicz();
wypisz();
}
koniec:

return 0;
}
[/cpp]

What's wrong with my code. Thanks a lot.[/cpp]

[alu_mathics]

i thing bfs is sufficient for this problem.
i solved the problem using bfs.
if i visit from u 2 v,
then i considered whether d[v]>d+1.
if yes i just update it.
and finally checked which index contains the maximum distance.
thats all.

[tlucz]

Thanks for the answer. But I would like somebody to test my program with input data and give me data for which my program generates wrong answer. Sorry for my english. Thanks.