fork download
copy 
  1. /*Check if a given graph is a tree */
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define MAX_V 10000
  6. #define MAX_A 20000
  7.  
  8. typedef struct
  9. {
  10.     int v; // vértice adjacente
  11. } TAdj;
  12.  
  13. vector<TAdj> adj[MAX_V]; // Lista de adjacência
  14.  
  15. int grau[MAX_V];
  16. // número de arestas do vértice
  17. void initGrafo(int qtdeVertices)
  18. {
  19.     memset(grau, 0, sizeof(grau));
  20.     for (int i = 0; i < qtdeVertices; i++)
  21.         adj[i].clear();
  22. }
  23.  
  24. // Cria aresta de a para b, com peso w
  25. void aresta(int a, int b)
  26. {
  27.     TAdj aux;
  28.     aux.v = b;
  29.     grau[a]++;
  30.     adj[a].push_back(aux);
  31.  
  32.     aux.v = a;
  33.     grau[b]++;
  34.     adj[b].push_back(aux);
  35.  
  36.     // Se o grafo for não orientado, também adicionamos a aresta (b, a) com
  37. }
  38.  
  39. int visitado[MAX_V];
  40. int p[MAX_V];
  41. int ordemVis;
  42.  
  43. void initDfs()
  44. {
  45.     memset(visitado, 0, sizeof(visitado));
  46.     memset(p, -1, sizeof(p));
  47.     ordemVis = 0;
  48. }
  49.  
  50. void dfs(int s)
  51. {
  52.     visitado[s]++;
  53.     for (auto t : adj[s])
  54.     {
  55.         if (visitado[t.v] == 0)
  56.         {
  57.             p[t.v] = s;
  58.             dfs(t.v);
  59.         }
  60.     }
  61. }
  62.  
  63. int main()
  64. {
  65.  
  66.     initDfs();
  67.  
  68.     int n, m;
  69.     int u, v;
  70.     cin >> n >> m;
  71.     initGrafo(n);
  72.     if (m == n - 1)
  73.     {
  74.         bool sai = false;
  75.         for (int i = 0; i < m; i++)
  76.         {
  77.             cin >> u >> v;
  78.             aresta(u, v);
  79.         }
  80.         dfs(u);
  81.         for (int i = 1; i <= n && !sai; i++)
  82.         {
  83.             if (visitado[i] != 1)
  84.             {
  85.                 sai = true;
  86.             }
  87.         }
  88.  
  89.         sai ? printf("NO\n") : printf("YES\n");
  90.     }
  91.     else
  92.     {
  93.         printf("NO\n");
  94.     }
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/h2NKmn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year ago
visibility:
public

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!