Advertisement
Guest User

DFS

a guest
Jul 18th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. int n,node[100][100],visit[100]= {0},c;
  5. int dfs(int st)
  6. {
  7. if(visit[st]==0)
  8. {
  9. visit[st]=1;
  10. //cout<<st+1<<endl;
  11. for(int i=0; i<n; i++)
  12. {
  13. if(node[st][i]==1 && visit[i]==0)
  14. {
  15. dfs(i);
  16. }
  17.  
  18. }
  19. }
  20. }
  21.  
  22. int main()
  23. {
  24. int i,j,st;
  25. freopen("input1.txt","r",stdin);
  26. cin>>n;
  27.  
  28. for(i=0; i<n; i++)
  29. {
  30. for(j=0; j<n; j++)
  31. {
  32. cin>>node[i][j];
  33. }
  34. }
  35. for(j=0; j<n; j++)
  36. {
  37. visit[j]=-1;
  38. c=0;
  39. for(i=0; i<n; i++)
  40. {
  41. if(visit[i]==0)
  42. {
  43. dfs(i);
  44. c++;
  45. }
  46. }
  47. if(c>1)
  48. {
  49. cout<<j+1<<endl;
  50. }
  51. memset(visit,0,sizeof(visit));
  52. }
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement