TLE in Ada and Cycle on SPOJ

@hblord787 I am unable to see the solution, can you share it here itself, or maybe provide a link to the Ideone page?

2 Likes

Sorry i am not really used to with spoj :grimacing:
Below is the code

#include<bits/stdc++.h>
using namespace std;
const int N=2222;
const int inf=0x3f3f3f3f;
vector<int>vv[N];
bool vis[N];
int ans;
int n;
typedef pair<int,int> p;
 
 
int bfs(int i)
{
    queue<p>q;
    q.push(make_pair(0,i));
 
    while(!q.empty())
    {
        int top=q.front().second;
        int dis=q.front().first;
        q.pop();
        for(int j=0;j<vv[top].size();j++)
        {
            int tem=vv[top][j];
            if(!vis[tem])
            {
                vis[tem]=1;
                if(tem==i)
                    return  dis+1;
                    q.push(make_pair(dis+1,tem));
            }
 
        }
    }
    return inf;
}
int main()
{
    cin>>n;
    int tem;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&tem);
            if(tem)
            {
                vv[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=inf;
        if(vv[i].size())
        {
            memset(vis,false,sizeof(vis));
            ans=bfs(i);
        }
        if(ans==inf)
        {
            puts("NO WAY");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
} 

1 Like

for(int i=1;i<=n;i++){
ll done =0;
vectorvis(n+1 ,0);
queue<pair<ll ,ll>>q;
q.push({i , 0});
vis[i] =1;
while(!q.empty()){
ll a = q.front().first;
ll len = q.front().second;
q.pop();

        for(auto it: adj[a]){
            if(vis[it] && it!=i) continue;
            if(vis[it]){
                cout<<len+1<<endl;
                done =1;
                break;
            }
            q.push({it , len+1});
            vis[it] =1;
        }
        if(done) break;
    }
    if(done==0) cout<<"NO WAY"<<endl; 
}