Program:-
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
vector<int>vec[n];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
vec[a].push_back(b);
vec[b].push_back(a);
}
vector<int>dist(n,-1);
dist[0]=0;//starting number is always 0..
queue<int>que;
que.push(0);
while(!que.empty()){
int index=que.front();que.pop();
for(int i=0;i<vec[index].size();i++){
if(dist[vec[index][i]]==-1){
dist[vec[index][i]]=dist[index]+1;
que.push(vec[index][i]);
}
}
}
if(n==1) cout<<"Not Cycle";
for(int i=1;i<n;i++){
set<int>st;
for(int j=0;j<vec[i].size();j++)
st.insert(dist[vec[i][j]]);
st.insert(dist[i]);
if(vec[i].size()>1 && st.size()<=vec[i].size()){ cout<<"Cycle";return 0;}
}
cout<<"Not Cycle";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
vector<int>vec[n];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
vec[a].push_back(b);
vec[b].push_back(a);
}
vector<int>dist(n,-1);
dist[0]=0;//starting number is always 0..
queue<int>que;
que.push(0);
while(!que.empty()){
int index=que.front();que.pop();
for(int i=0;i<vec[index].size();i++){
if(dist[vec[index][i]]==-1){
dist[vec[index][i]]=dist[index]+1;
que.push(vec[index][i]);
}
}
}
if(n==1) cout<<"Not Cycle";
for(int i=1;i<n;i++){
set<int>st;
for(int j=0;j<vec[i].size();j++)
st.insert(dist[vec[i][j]]);
st.insert(dist[i]);
if(vec[i].size()>1 && st.size()<=vec[i].size()){ cout<<"Cycle";return 0;}
}
cout<<"Not Cycle";
return 0;
}
pantagone will fail
ReplyDelete