An undirected/directed graph is a tree if anyone know that any two of the following three properties are true:
1. It is connected
2. There are n – 1 edges, where n is the number of nodes
3. There are no cycles
It is better to check if all these three conditions are true, then that graph is surely a tree.
This problem also can be solved with BFS, but I used DFS because of smaller size of code n more simplyness than BFS.
Here, the source is not given so I have assumed the 1st node of the 1st given edge to be the source with the help of a variable x, you can assume any of the node.
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loopn(i,n) for(int i=1;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopi(i,n) for(int i=0;i<n-1;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define loopba(i,b,a) for(int i=b;i>=a;i--)
#define REV(i,n) for(i=n; i>=0; i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 1000000
#define inf 100000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
vector<int>g[MAX+1];
bool visited[MAX+1];
int c,d;
void dfs(int u)
{
visited[u]=1;
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(visited[v]) //Checking cycle/loop
{
d=1;
break;
}
else
{
c++; // Checking connected
dfs(v);
}
}
}
int main()
{
CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int node,edge;
cin>>node>>edge;
int x=0,src;
for(int i=0; i<edge; i++)
{
int from,to;
cin>>from>>to;
if(x==0) src=from;
x=1;
g[from].push_back(to);
}
c=1; // Either the graph is connected or not(Either each vertex is visited once or not)
d=0; // For checking cycle/loop
visited[src]=1;
dfs(src);
if(!d && c==node && edge==node-1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
Fall out, Codes! 
I think the vector g should be vector<vector g rather than vector g
LikeLiked by 1 person
Thanks for your feedback.
The way you think the 2D vector g should be declared – vector< vector > g;
is correct. But the way I declared the 2D vector g, is just another way of declaring a 2D vector.
Example:
vector v[2]; //This means you are allocating v[0]={} and v[1]={}
//After decaring the vector, if you print this vector v like:
for(int i=0; i<4; i++)
{
cout<<v[i].size()<<endl;
}
If you run the above example, this program will give you the size of v[0] and v[1] (rows) as 0, since I have declared the vector as v[2].
And for rows no. 2 and 3 (v[2] and v[3]), it will give any garbage value. That means there is nothing right now but you can still push values in v[2]/v[3] or in any other index still, though I declared it initially as v[2]. This can be done due to the dynamic nature of the vector.
As I know how many rows the vector g can have, which is MAX value, I declared that in this way. The code runs without any error and it is an accepted code in SPOJ online judge!
LikeLike
@oumyaraj biswal, another thing, notice how I am processing the input at first i.e. pushing data to the 2D vector ‘g’ to build the adjacency matrix – by the following syntax:
g[from].push_back(to);
Now one important factor about 2D vector insertion is-
If initially, you do not have any values in the vector – You can push values into one vector and then push this vector into the 2D vector. For example:
vector<vector > g;
vector gg;
gg.push_back(value);
g.push_back(gg);
If your vector is already populated then you can do –
g[index].push_back(value);
For this convenience, I have declared the 2D vector with a definite size(as I know the row size) which populates default data automatically and thus I can take the input in an easier way.
Hope this helps you in some way.
LikeLike