আলোচনাঃ
আমাকে একটা undirected,unweighted graph দেয়া হবে। Graph টা Tree(বিশেষ ধরনের graph) কিনা সেটা বলতে হবে।
তো একটা graph , tree হবে তখনই যখন-
1) edges=nodes-1, অর্থাত graph এ total edges হবে তার total nodes থেকে 1 কম।
2) full graph এ একটাই component থাকবে।
3) graph এ কোনো cycle থাকবে না। অর্থাত একটা node থেকে visit start করলে ঐ node এ দ্বিতীয়বার visit করা যাবে না। প্রতিটা node একবারই visit হবে।
এই 3টা জিনিস কোনো একটা graph এ থাকলেই কেবল আমরা ঐ graph কে tree বলতে পারবো। আর tree তে একটা node থেকে আরেকটা node এ যাওয়ার জন্য অবশ্যই একটা path থাকবেই।
তো আমরা tree এর properties জানলাম। এখন এই properties গুলো আমাদের given graph এ আছে কিনা সেটা check করলেই হবে।যদি থাকে তাহলে YES প্রিন্ট করবো। নাহয় NO প্রিন্ট করবো।
উত্তরঃ
যেহেতু আমাকে node=n and edge=m (সাধারণত node কে n, আর edge কে m দিয়ে প্রকাশ করা হয়) দেয়াই থাকবে তো আমরা সহজেই 1no property check করতে পারবো।
এখন 2nd property check করা লাগবে। Component কি সেটা নিচের ছবিতে এঁকে দেখানো হলো।
green color এর তিনটা region হচ্ছে একেকটা component. তার মানে উপরের graph এ তিনটা component আছে। যেখানে প্রথম component এ node এর সংখ্যা 6টি, ২য় component এ একটা,৩য় component এ
দুইটা nodes আছে। যেহেতু 3টা component আছে,তাই এটা একটা graph,not tree.
dfs() দিয়ে সাধারণত component check করা যায়।
তো আমার কাছে যদি একটাই component থাকে তাহলে graph এর সকল node ঐ component এই থাকবে। এটা তো sure. তাই না?
তো আমরা dfs() চালানোর সময় কয়টা node visit করলাম সেটা count করে
রাখতে পারি। যদি count সংখ্যা , node সংখ্যার সমান হয় তবে সেখানে একটাই component আছে বলা যাবে।কিন্তু total component সংখ্যা কতো সেটা কিন্তু আমরা এভাবে বলতে পারবো না ।
এভাবে বের করলে বুঝতে পারবো ঐ graph এ একটা component আছে কিনা? নাকি 1 থেকে বেশি। যদি একের বেশি component হয় তাহলে total কয়টা component আছে তা এভাবে বলা possible না।
total component সংখ্যা বের করার জন্য আমদের প্রতিটা node থেকে dfs() চালানো লাগবে। total কয়টা dfs() চললো সেটার count রাখলেই হবে।
তো এই problem এ যেহেতু আমাকে graph টা tree কিনা সেটা check করলেই হবে তাই count সংখ্যা , node সংখ্যার সমান কিনা সেটা check করলেই হবে। total component বের করলেও হবে। problem নেই।
আর বাকি রইলো cycle আছে কিনা তা check করা। এটা আমরা dfs() এর মধ্যেই check করতে পারি। যদি কোনো node একের অধিক বার visit হয় তাহলেই আমরা বুঝবো সেখানে cycle আছে। তখন false return করতে পারি এবং বলে দিতে পারি সেটা tree না।
উপরের চিত্রে , 1no component এ যদি node 1 থেকে dfs() start করি, তারপর কোনো এক সময় আবার node 1 এ আসবে যেহেতু (1-2-3-4) একটা cycle আছে।
আর node=1 কিন্তু already visited একটা node. এর জন্য code এর else{} এ আসবে and cycle থাকায় true return করবে।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+10;
vector<int> gr[N];
bool vis[N];
int n,m;
bool cycle;
int cnt;
void dfs(int src)
{
vis[src]=1;
for(auto v:gr[src]){
if(!vis[v]){
cnt++;
dfs(v);
}
else{
cycle=true;
break;
}
}
}
int main()
{
int c,u,v,sr=0;
cin>>n>>m;
int edge=m;
while(m--){
cin>>u>>v;
if(sr==0) sr=u; // take first node as a starting for dfs
// you can choose any node
gr[u].push_back(v);
}
cnt=1; // source node is always encountered.That's why cnt=1
cycle=false;
memset(vis,0,sizeof(vis));
dfs(sr);
if(connected==n && edge==n-1 && !cycle){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
------------------------------- OR -------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+10;
vector<int> gr[N];
bool vis[N];
int n,m;
void dfs(int src)
{
vis[src]=1;
for(auto v:gr[src]){ // v is the adjacent of 'src' node
if(!vis[v]){
dfs(v);
}
}
}
int main()
{
int u,v;
cin>>n>>m;
int edge=m;
while(m--){
cin>>u>>v;
gr[u].push_back(v);
gr[v].push_back(u);
}
int dfsCount=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){// total component number checking
if(vis[i]==0){
dfs(i);
dfsCount++;
}
}
if(dfsCount==1 && edge==n-1){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
Related problem – Oil Deposits