fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. class Graph
  4. {
  5.     int v;
  6.     list<int> *adj;
  7. public:
  8.     Graph(int v);
  9.     void addEdge(int v,int w);
  10.     void DFS(int s);
  11. };
  12. Graph::Graph(int v)
  13. {
  14.     this->v=v;
  15.     adj=new list<int>[v];
  16. }
  17. void Graph:: addEdge(int v,int w)
  18. {
  19.     adj[v].push_back(w);
  20.     adj[w].push_back(v);
  21. }
  22. void Graph:: DFS(int s)
  23. {
  24.     int fvar=s;
  25.     int flag=1;
  26.     vector<bool> visited(v,false);
  27.     stack<int> stk;
  28.     vector<int>parent(v,-1);
  29.     stk.push(s);
  30.     while(!stk.empty() && flag!=0){
  31.         s=stk.top();
  32.         stk.pop();
  33.         if(!visited[s]){
  34.             visited[s]=true;
  35.         }
  36.         list<int>:: iterator it;
  37.         for(it=adj[s].begin();it!=adj[s].end();it++){
  38.  
  39.             if(!visited[*it]){
  40.                 parent[*it]=s;
  41.                 stk.push(*it);
  42.             }
  43.         if(visited[*it] && parent[s]!=*it){
  44.             flag=0;
  45.             break;
  46.         }
  47.         }
  48.     }
  49.     vector<bool>:: iterator it1;
  50.     for(it1=visited.begin();it1!=visited.end();it1++){
  51.         if(visited[*it1]==false){
  52.             flag=0;
  53.             break;
  54.         }
  55.     }
  56.     if(flag==0)
  57.         cout<<"NO"<<endl;
  58.     else
  59.         cout<<"YES"<<endl;
  60. }
  61. int main()
  62. {
  63.     int i,m,x,y,v;
  64.     cin>>v>>m;
  65.     Graph g(v);
  66.     for(i=1;i<=m;i++){
  67.         cin>>x>>y;
  68.         g.addEdge(x-1,y-1);
  69.     }
  70.  
  71.     g.DFS(x-1);
  72.     return 0;
  73. }
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
Success #stdin #stdout 0s 4436KB
comments (?)
stdin
copy 
3 2
1 2
2 3
stdout
copy 
YES
https://ideone.com/I2PsWI
problem PT07Y, based on SPOJ submission 25356144 (CPP14), 2020-02-04 20:43:07
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!