@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
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;
}