awfulcode.cpp

// program is to find if the given graph is tree or not.
#include <cstdio>
#include <vector>
using namespace std;
vector < int > adj[10048];

// this is the recursion depth the node was processed at or
// 0 if it hasn't been processed yet
int d[10048];
 
bool has_cycle(int current_node, int recursion_depth){
	
    d[current_node] = recursion_depth;

	// go through each adjacency for the current node
	for(auto current_adj : adj[current_node]) {

		// if we've seen a node adjacent to us and it wasn't the node that we just checked, 
		//   it's a cycle.   Recursion_depth - 1 is our parent stack, so if it's less than 
		//   recursion depth - 1 it means we saw it a "long time ago", so it's a cycle
        if(d[current_adj] && d[current_adj] < recursion_depth - 1) return true;
		
		// if the current adjacency has been seen but it's recursion depth was
		//   our parent (== recursion_depth - 1) (this makes sense) OR
		//   it was a much deeper recursive call ignore it (this doesn't make sense) 
		
		
		// if the current adj hasn't been processed
        if(!d[current_adj])
			// if a cycle is ever found, the program will always
			//   say "NO" so no reason to keep looking
            if(has_cycle(current_adj, dep + 1)) {
				return true;
			}
    }
    return false;
}
 
int main(void){
    int a, b, i, edge_count, node_count, r; scanf("%d %d", &node_count, &edge_count);
    // n- number of nodes, m-number of edges
	
	// mark d as unknown for every node
    for(int i = 0; i < node_count; ++i)
        d[i] = 0;
		
	// load up the topography from user
    for(i = 0; i < edge_count; ++i){
        scanf("%d %d", &a, &b);
        // a and b are the nodes which are connected.
        // why -- first?
		--a; --b; /* 0-base a and b */
		
		// mark a as adjacent to b and b as adjacent to a
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
		
	// it's "ok" if no cycle was detected
    bool ok = !has_cycle(0, 1);
	
	// if there is NOT a cycle AND every node was visited by following adjacencies from node 0
    for(int i = 0; i < n && ok; ++i)
        ok &= !!d[i]; // 0 becomes false, non-0 becomes true
    puts(ok ? "YES" : "NO");
    return 0;
}