Cicluri elementare
Fiind dat G=(V,E) un graf conex , se cere sa separe n-1 muchii ale unui arbore partial si m-(n-1) muchii care nu fac parte din acesta. |
#include<iostream>
#include<fstream> using namespace std; int s[50],A[50][50],T[50],gasit,n,st; void CitireN(char Nume_fis[20],int A[50][50],int& n) { int i,j; fstream f(Nume_fis,ios::in); f>>n; while(f>>i>>j) A[i][j]=A[j][i]=1; f.close(); } void ciclu (int k) { cout<<st<<" "; while (k!=st) { cout<<k<<" "; k=T[k]; } cout<<st<<endl; } void df(int nod) { int k; s[nod]=1; for(k=1;k<=n;k++) if(A[nod][k]==1) { A[k][nod]=0; if(s[k]==0) { T[k]=nod; s[k]=1; df(k); } else { gasit=1; st=k; ciclu(nod); } } } main() { CitireN("Graf.txt",A,n); df(1); if(!gasit) cout<<" Graful nu contine cicluri"; } 5 1 2 1 4 1 5 2 3 2 4 3 4 4 5 |