Advertisement
cojoc

Untitled

May 23rd, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.77 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. ifstream f("input.in");
  5.  
  6. int ma[100][100],n,m,viz[100],st[100],vf,nrc;
  7.  
  8. void citire(){
  9. f>>n>>m;
  10. int i,x,y;
  11. for(i=1;i<=m;i++){
  12. f>>x>>y;
  13. ma[x][y]=ma[y][x]=1;
  14. }
  15. f.close();
  16. }
  17.  
  18. void dfs(int x,int nr){
  19. int i,y;
  20. vf=1;
  21. st[vf]=x;
  22. viz[x]=nr;
  23. while(vf){
  24. y=st[vf];//y nod curent
  25. for(i=1;i<=n;i++)if(ma[y][i]&&viz[i]==0){
  26. viz[i]=nr;
  27. st[++vf]=i;
  28. break;
  29. }
  30. if(i>n)--vf;
  31. }
  32. }
  33. void rezolvare(){
  34. int x,nr,gasit,i;
  35. x=1;
  36. nr=1;
  37. do{
  38. gasit=0;
  39. dfs(x,nr);
  40. for(i=1;i<=n;i++)if(viz[i]==0){
  41. x=i;
  42. gasit = 1;
  43. ++nr;
  44. break;
  45. }
  46. }while(gasit);
  47. cout<<nr<<" componente conexe";
  48. }
  49. int main(){
  50. citire();
  51. rezolvare();
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement