02/01 - Probleme parcurgere in adancime

Se citeste nr de noduri, nr de muchii si muciile. Sa se verifice daca doua noduri x,y fac parte din aceeasi componenta conexa. Sa se verifice daca graful este conex. Sa se afiseze componentele conexe ale grafului. Sa se afiseze componenta conexa de lungime maxima. Afisati muchiile care trebuie adaugate pentru ca graful sa devina conex.

#include<iostream>
#include<fstream>
using namespace std;
int a[20][20],n,m,v[20],xx,yy,u[10][10];
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
a[x][y]=a[y][x]=1;}
f>>xx>>yy;
}

void DF(int x)
{//cout<<x<<" ";
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DF(i);
}

void DDF(int x)
{//cout<<x<<" ";
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        {cout<<x<<" "<<i<<endl;
                        DDF(i);
        }
}

void DFF(int x,int &j,int &k)
{cout<<x<<" ";
u[j][k]=x;
k++;
v[x]=1;
for(int i=1;i<=n;i++)
    if(a[x][i]==1 && v[i]==0)
        DFF(i,j,k);
}

int main()
{citire();
int ok=1,k=0,maxi=0,j=0,p;
DF(xx);
if(v[yy]==1)
    cout<<xx<<" si "<<yy<<" fac parte din aceeasi componenta conexa";
else cout<<xx<<" si "<<yy<<" NU! fac parte din aceeasi componenta conexa";
for(int i=1;i<=n;i++)
    v[i]=0;
DF(1);
for(int i=1;i<=n;i++)
    if(v[i]==0)
        ok=0;
if(ok)
    cout<<endl<<"Graful este conex"<<endl;
else cout<<endl<<"Graful nu este conex"<<endl;

for(int i=1;i<=n;i++)
    v[i]=0;
cout<<"Componentele conexe "<<endl;
for(int i=1;i<=n;i++)
    if(v[i]==0)
    {DFF(i,j,k);
    j++;
    if(k>maxi)
        maxi=k;
    k=0;
    cout<<endl;
    }
cout<<"Cea mai lunga componenta conexa ("<<maxi<<") "<<endl;
for(int i=0;i<j;i++)
    if(u[i][maxi-1]!=0)
        p=i;
for(int i=0;i<maxi;i++)
    cout<<u[p][i]<<" ";
cout<<endl<<"Pentru ca graful sa devina conex trebuie adaugate muchiile"<<endl;
for(int i=1;i<j;i++)
    cout<<u[0][0]<<" "<<u[i][0]<<endl;
for(int i=1;i<=n;i++)
    v[i]=0;
cout<<"Muchiile de avansare"<<endl;
for(int i=1;i<=n;i++)
    if(v[i]==0)
        DDF(i);

}

Fisier

10 7
1 2
1 3
2 3
1 10
6 8
4 5
5 7
2 8

Graf bipartit - !!UNCOMPLITID!!

#include<iostream>
#include<fstream>
using namespace std;
int u[100][100],a[10],b[10],n,m,v[10];
void citire()
{ifstream f("date");
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{f>>x>>y;
u[x][y]=u[y][x]=1;}

}

void DF(int x,int &i, int &j)
{
v[x]=1;
for(int ii=1;ii<=n;ii++)
    if(u[x][ii]==1 && v[ii]==0)
        {if(a[i-1]==x)
            {b[j]=ii;j++;}
        if(b[j-1]==x)
            {a[i]=ii;i++;}
            DF(ii,i,j);
        }
}

int main()
{    citire();
    a[0]=1;  
    int i=1,j=0;
    DF(1,i,j);
    for(int ii=0;ii<i;ii++)
        cout<<a[ii]<<" ";
    cout<<endl;
    for(int ii=0;ii<j;ii++)
        cout<<b[ii]<<" ";
 
}

Fisier

6 5
1 5
2 3
3 4
5 6
3 6