Matrice de adiacenta

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("Graph.in");

class UndirectedGraph
{
    int nE,nV,m[15][15];
public:
    void read();
    void showEdges();
    void bfs(int start);
    int* dfs(int start, bool enablePrinting);
    UndirectedGraph complement();
    void showDegrees();
    void showVerticesAscDegree();
    void showVerticesEvenDegree();
    void countEvenUnevenDegrees();
    bool isRegular();
    bool isConnected();
    void showConnectedComponents();
    bool isComplete();
    bool hasIsolaTedNodes();
    bool isChain(int v[], int n);
    void cyclesDFS(int currentNode, int parent, bool *flag, int v[]);
    bool hasCycles();
    bool isTree();
    void chainBack1(int st[], int k);
    void showChains();
    void chainBack2(int st[], int k, int sol[], int *maxLength);
    void showLongestChain();
    void bipartiteBFS(int currentNode, bool *flag, int v[]);
    bool isBipartite();
    void showRequiredConnectingEdges();
};

class DirectedGraph
{
    int nE,nV,m[15][15];
public:
    void read();
    void showEdges();
    void showIndegreesOutdegrees();
    void showStrongConnectedComponents();

};

int main()
{
    UndirectedGraph g;
    g.read();
    g.showEdges();
    g.showRequiredConnectingEdges();
    /*
    DirectedGraph g;
    g.read();
    g.showEdges();
    g.showIndegreesOutdegrees();
    g.showStrongConnectedComponents();
    */
    return 0;
}

void UndirectedGraph::read()
{
    int i,j,V1,V2;

    f>>nV>>nE;
    for(i=0;i<nV;i++)
        for(j=0;j<nV;j++)
            m[i][j]=0;
    i=0;
    for(i=0;i<nE;i++)
    {
        f>>V1>>V2;
        if(V1<nV&&V2<nV)
        {
            m[V1][V2]=1;
            m[V2][V1]=1;
        }
    }

}

void UndirectedGraph::showEdges()
{
    int i,j;
    cout<<endl<<nV<<' '<<nE<<endl<<"E={ ";
    for(i=0;i<nV;i++)
    {
        for(j=i+1;j<nV;j++)
        {
            if(m[i][j]==1)
                cout<<"{"<<i<<","<<j<<"}";
        }

    }
    cout<<" }";
    /*
    cout<<endl;
    for(i=0;i<nV;i++)
    {
        for(j=0;j<nV;j++)
            cout<<m[i][j]<<' ';
        cout<<endl;
    }
    */
}

void UndirectedGraph::bfs(int start)
{
    int q[15],v[15],pos=0,nr=1,i;
    q[pos]=start;
    for(i=0;i<nV;i++)
        v[i]=0;
    v[start]=1;
    while(pos<nr)
    {
        for(i=0;i<nV;i++)
            if(m[q[pos]][i]&&!v[i])
            {
                q[nr++]=i;
                v[i]=1;
            }
        pos++;
    }
    cout<<endl<<"BFS("<<start<<"): ";
    for(i=0;i<nr;i++)
        cout<<q[i]<<' ';
}

int* UndirectedGraph::dfs(int start,bool enablePrinting)
{
    int *s,*v,pos=0,i;
    s=new int[nV];
    v=new int[nV];
    s[pos]=start;
    for(i=0;i<nV;i++)
        v[i]=0;
    v[start]=1;
    if(enablePrinting)
        cout<<endl<<"DFS("<<start<<"): ";
    while(s[0]!=-1)
    {
        if(v[s[pos]]!=2&&enablePrinting)
            cout<<s[pos]<<' ';
        v[s[pos]]=2;
        for(i=0;i<nV;i++)
            if(m[s[pos]][i]&&!v[i])
            {
                s[++pos]=i;
                v[i]=1;
                break;
            }
        if(i==nV)
            s[pos--]=-1;
    }
    return v;
}

UndirectedGraph UndirectedGraph::complement()
{
    UndirectedGraph g;
    int i,j;
    g.nV=nV;
    g.nE=nE*(nE-3)/2;
    for(i=0;i<g.nV;i++)
        for(j=0;j<g.nV;j++)
            if(i!=j)
                g.m[i][j]=1-m[i][j];
    return g;
}

void UndirectedGraph::showDegrees()
{
    int i,j,s;
    cout<<endl<<"v     ";
    for(i=0;i<nV;i++)
        cout<<i<<' ';
    cout<<endl<<"d(v)  ";
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        cout<<s<<' ';
    }
}

void UndirectedGraph::showVerticesAscDegree()
{
    int i,j,v[15],d[15],aux,s;
    for(i=0;i<nV;i++)
        v[i]=i;
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        d[i]=s;
    }
    for(i=0;i<nV-1;i++)
        for(j=i+1;j<nV;j++)
            if(d[i]>d[j])
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
                aux=d[i];
                d[i]=d[j];
                d[j]=aux;
            }
    cout<<endl<<"Varfurile in ordinea crescatoare a gradului sunt: ";
    for(i=0;i<nV;i++)
        cout<<v[i]<<' ';
    cout<<endl<<"Gradul minim este "<<d[0]<<", iar gradul maxim este "<<d[nV-1]<<'.'<<endl;
}

void UndirectedGraph::showVerticesEvenDegree()
{
    int i,j,aux,s;
    cout<<endl<<"Varfurile cu grad par sunt: ";
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        if(s%2==0)
            cout<<i<<' ';
    }
}

void UndirectedGraph::countEvenUnevenDegrees()
{
    int i,j,s,evenCount=0,unevenCount=0;
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        if(s%2)
            unevenCount++;
        else
            evenCount++;
    }
    cout<<endl<<"Graful are "<<evenCount<<" noduri cu grad par si "<<unevenCount<<" noduri cu grad impar."<<endl;
}

bool UndirectedGraph::isRegular()
{
    int i,j,d[15],s;
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        d[i]=s;
    }
    for(i=0;i<nV-1;i++)
        if(d[i]!=d[i+1])
            return false;
    return true;
}

bool UndirectedGraph::isConnected()
{
    int *v=this->dfs(0,false),i;
    for(i=0;i<nV;i++)
        if(v[i]==0)
            return false;
    return true;
}

void UndirectedGraph::showConnectedComponents()
{
    int n=1,*v1=this->dfs(0,false),*v2,i,j;
    cout<<endl<<"Componenta conexa "<<n<<": ";
    for(i=0;i<nV;i++)
    {
        if(v1[i]!=0)
        {
            cout<<i<<' ';
        }
    }
    for(j=0;j<nV;j++)
    {
        if(v1[j]==0)
        {
            v2=this->dfs(j,false);
            cout<<endl<<"Componenta conexa "<<++n<<": ";
            for(i=0;i<nV;i++)
            {
                if(v2[i]!=0)
                {
                    cout<<i<<' ';
                    v1[i]=v2[i];
                }
            }
            delete v2;
        }
    }
    cout<<endl<<"Graful este "<<100./n<<"% conex";
}

bool UndirectedGraph::isComplete()
{
    int i,j;
    for(i=0;i<nV;i++)
        for(j=0;j<nV;j++)
            if(i!=j&&!m[i][j])
                return false;
    return true;
}

bool UndirectedGraph::hasIsolaTedNodes()
{
    int i,j,s;
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        if(!s)
            return true;
    }
    return false;
}

bool UndirectedGraph::isChain(int v[],int n)
{
    int i;
    for(i=1;i<n;i++)
        if(!m[v[i-1]][v[i]])
            return false;
    return true;
}

void UndirectedGraph::cyclesDFS(int currentNode, int parent, bool *flag, int v[])
{
    int i;
    v[currentNode]=1;
    for(i=0;i<nV;i++)
        if(m[currentNode][i])
            if(v[i])
            {
                if(i!=parent)
                {
                    *flag=true;
                }
            }
            else
                this->cyclesDFS(i,currentNode,flag,v);
}

bool UndirectedGraph::hasCycles()
{
    bool flag=false;
    int i,v[nV];
    for(i=0;i<nV;i++)
        v[i]=0;
    this->cyclesDFS(0,-1,&flag,v);
    return flag;
}

bool UndirectedGraph::isTree()
{
    if(this->isConnected()&&!this->hasCycles())
        return true;
    return false;
}

void UndirectedGraph::chainBack1(int st[], int k)
{
    int i,j,ok;
    if(k>2)
    {
        cout<<endl;
        for(i=0;i<k;i++)
            cout<<st[i]<<' ';
    }
    if(k<nV)
    {
        for(i=0;i<nV;i++)
        {
            //cout<<i<<' ';
            ok=1;
            for(j=0;j<k;j++)
                if(st[j]==i)
                {
                    ok=0;
                    break;
                }
            if(k>0)
                if(!m[st[k-1]][i])
                    ok=0;
            if(ok)
            {
                st[k]=i;
                this->chainBack1(st,k+1);
            }
        }
    }
}

void UndirectedGraph::showChains()
{
    int st[nV];
    this->chainBack1(st,0);
}

void UndirectedGraph::chainBack2(int st[], int k, int sol[], int *maxLength)
{
    int i,j,ok;
    if(k>*maxLength)
    {
        *maxLength=k;
        for(i=0;i<k;i++)
            sol[i]=st[i];
    }
    if(k<nV)
    {
        for(i=0;i<nV;i++)
        {
            ok=1;
            for(j=0;j<k;j++)
                if(st[j]==i)
                {
                    ok=0;
                    break;
                }
            if(k>0)
                if(!m[st[k-1]][i])
                    ok=0;
            if(ok)
            {
                st[k]=i;
                this->chainBack2(st,k+1,sol,maxLength);
            }
        }
    }
}

void UndirectedGraph::showLongestChain()
{
    int st[nV], sol[nV], maxLength=0, i;
    this->chainBack2(st,0,sol,&maxLength);
    cout<<endl;
    if(maxLength<3)
        cout<<"Graful nu are niciun lant";
    else
    {
        cout<<"Cel mai lung lant este: ";
        for(i=0;i<maxLength;i++)
            cout<<sol[i]<<' ';
    }
}

void UndirectedGraph::bipartiteBFS(int currentNode, bool *flag, int v[])
{
    int i,foundColor1=0,foundColor2=0;
    for(i=0;i<nV;i++)
        if(m[currentNode][i])
            if(v[i]==1)
                foundColor1=1;
            else if(v[i]==2)
                foundColor2=1;
    if(!foundColor1)
        v[currentNode]=1;
    else
    {
        if(!foundColor2)
            v[currentNode]=2;
        else
            *flag=false;
    }
    if(*flag==false)
        return ;
    for(i=0;i<nV;i++)
        if(m[currentNode][i]&&!v[i])
            this->bipartiteBFS(i,flag,v);
}

bool UndirectedGraph::isBipartite()
{
    bool flag=true;
    int i,v[nV];
    for(i=0;i<nV;i++)
        v[i]=0;
    this->bipartiteBFS(0,&flag,v);
    return flag;
}

void UndirectedGraph::showRequiredConnectingEdges()
{
    int n=1,v[nV],*v1=this->dfs(0,false),*v2,i,j;
    v[0]=0;
    for(j=0;j<nV;j++)
    {
        if(v1[j]==0)
        {
            v[n++]=j;
            v2=this->dfs(j,false);
            for(i=0;i<nV;i++)
                if(v2[i]!=0)
                    v1[i]=v2[i];
            delete v2;
        }
    }
    if(n==1)
        cout<<endl<<"Graful este deja conex";
    else
    {
        cout<<endl<<"Pentru ca graful sa devina conex, se pot adauga urmatoarele muchii: ";
        for(i=0;i<n-2;i++)
            cout<<'('<<v[i]<<','<<v[i+1]<<"), ";
        cout<<'('<<v[n-2]<<','<<v[n-1]<<')';
    }

}

void DirectedGraph::read()
{
    int i,j,V1,V2;

    f>>nV>>nE;
    for(i=0;i<nV;i++)
        for(j=0;j<nV;j++)
            m[i][j]=0;
    i=0;
    for(i=0;i<nE;i++)
    {
        f>>V1>>V2;
        if(V1<nV&&V2<nV)
            m[V1][V2]=1;
    }

}

void DirectedGraph::showEdges()
{
    int i,j;
    cout<<endl<<nV<<' '<<nE<<endl<<"E={ ";
    for(i=0;i<nV;i++)
    {
        for(j=0;j<nV;j++)
        {
            if(m[i][j]==1)
                cout<<"{"<<i<<","<<j<<"}";
        }

    }
    cout<<" }";
    /*
    cout<<endl;
    for(i=0;i<nV;i++)
    {
        for(j=0;j<nV;j++)
            cout<<m[i][j]<<' ';
        cout<<endl;
    }
    */
}

void DirectedGraph::showIndegreesOutdegrees()
{
    int i,j,s;
    cout<<endl<<"v      ";
    for(i=0;i<nV;i++)
        cout<<i<<' ';
    cout<<endl<<"d+(v)  ";
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[i][j];
        cout<<s<<' ';
    }
    cout<<endl<<"d-(v)  ";
    for(i=0;i<nV;i++)
    {
        s=0;
        for(j=0;j<nV;j++)
            s+=m[j][i];
        cout<<s<<' ';
    }
}

void DirectedGraph::showStrongConnectedComponents()
{
    int md[15][15],v[15],i,j,k,n=0;
    for(i=0;i<nV;i++)
    {
        v[i]=0;
        for(j=0;j<nV;j++)
            md[i][j]=m[i][j];
    }
    for(k=0;k<nV;k++)
        for(i=0;i<nV;i++)
            for(j=0;j<nV;j++)
                if(k!=i&&k!=j&&!md[i][j])
                    md[i][j]=md[i][k]*md[k][j];
    cout<<endl;
    for(i=0;i<nV;i++)
    {

        for(j=0;j<nV;j++)
            cout<<md[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
    for(i=0;i<nV;i++)
    {
        if(!v[i])
        {
            cout<<"Componenta tare conexa "<<++n<<": "<<i<<' ';
            v[i]=1;
            for(j=0;j<nV;j++)
                if(i!=j&&md[i][j]*md[j][i])
                {
                    v[j]=1;
                    cout<<j<<' ';
                }
            cout<<endl;
        }

    }

}