Advertisement
HmHimu

undirected graph(connected/not)

Jul 20th, 2017
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1.  
  2. #include<iostream>
  3. using namespace std;
  4. int adj[100][100],v,time;
  5. int color[100];
  6. void DFS_Visit(int u);
  7. void DFS()
  8. {
  9. for(int i=1;i<=v;i++)
  10. {
  11. time++;
  12.  
  13. color[i]=0;
  14.  
  15.  
  16. DFS_Visit(i);
  17. }
  18. }
  19. void DFS_Visit(int u)
  20. {
  21. color[u]=1;
  22.  
  23. for(int i=1;i<=v;i++)
  24. {
  25. int k=adj[u][i];
  26. if(k==1&&color[i]==0)
  27. {
  28. DFS_Visit(i);
  29. }
  30. }
  31. color[u]=2;
  32.  
  33. }
  34.  
  35. int main()
  36. {
  37. int a,b,k=1;
  38. cout<<"Input Vertex Number :";
  39. cin>>v;
  40. k=1;
  41. do
  42. {
  43. cout<<"Edge "<<k<<" : ";
  44. cin>>a>>b;
  45. if( a>v || b>v)
  46. {
  47. cout<<"Invalid Input,try again... "<<endl;
  48. }
  49. else if(a<=0 || b<=0)
  50. {
  51.  
  52. break;
  53. }
  54. else
  55. {
  56. adj[a][b]=1;
  57. adj[b][a]=1;
  58. k++;
  59. }
  60. }while(a!=0 && b!=0);
  61.  
  62.  
  63.  
  64. DFS();
  65. if(time==v)
  66. {
  67. cout<<"connected"<<endl;
  68.  
  69. }
  70. else{
  71. cout<<"Not connected";
  72. }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement