#include <bits/stdc++.h>

using namespace std;
int const MAXN = 1000;
int A[MAXN][MAXN];
int visited[MAXN];
int n,m,directed;
vector<int> connected;

void readGraph (){
    printf ("Is the graph Directed or Undirected ? [1/0]: ");
    scanf ("%d",&directed);
    printf ("Number of graph nodes: ");
    scanf ("%d",&n);
    printf ("Number of graph edges: ");
    scanf ("%d",&m);
    printf("Enter the %d edges:\n",m);
    printf ("Edge u -> v : \n");
    for (int i=0;i<m;i++){
        int u,v;
        printf("Enter u and v \n ");
        scanf ("%d %d",&u,&v);

        A[u][v]=1;
        if (directed==0) A[v][u]=1;
    }
}
void displayGraph (){
    printf ("Adjacency matrix : \n");
    printf ("      ");
    for (int i =1;i<=n;i++)
        printf (" %2d  ",i);
    puts("");
    for (int i=1;i<=n;i++){
        printf (" %2d | ",i);
        for (int j=1;j<=n;j++)
            printf (" %2d  ",A[i][j]);
        puts("");
    }
}
void order(){
    printf ("Graph order: %2d \n",n);
}
void numberOfLinks(){
    printf ("Number of links: %2d \n",m);
}
void density(){
    printf ("Graph density: %2f \n",2*m/((double)n*(n-1)));
}
int outDegree (int s){
    int out=0;
    for (int i=1;i<=n;i++)
        out+=A[s][i];
    return out;
}
int inDegree (int s){
    int in=0;
    for (int i=1;i<=n;i++)
        in+=A[i][s];

    return in;
}
void degree(){
    int s;
    printf ("Enter the summet: ");
    scanf("%d",&s);
    if (directed){
        int out= outDegree(s);
        int in = inDegree(s);
        printf ("The outdegree of summet %2d is %2d\n",s,out);
        printf ("The indegree of summet %2d is %2d\n",s,in);
        printf ("The degree of summet %2d is %2d\n",s,in+out);
        return;
    }
    int d=0;
    for (int i=1;i<=n;i++)
        d+=A[s][i];
    printf ("The degree of summet %2d is %2d\n",s,d);
}
int countDegree(int s){
    int d=0;
    for (int i=1;i<=n;i++)
        d+=A[s][i];
    return d;
}
void voisinageSortant (int s){
    vector<int> v;
    for (int i=1;i<=n;i++){
        if (A[s][i]) v.push_back(i);
    }
    printf ("Le voisinage sortant du sommet %2d est [",s);
    for(int i=0; i<  static_cast<int>(v.size()); i++)
        if (i==(int)v.size()-1)
            printf ("%d]\n",v[i]);
        else printf("%d,",v[i]);
    if (v.size()==0){
        printf ("]\n");
    }
}
void voisinageEntrant (int s){
    vector<int> v;
    for (int i=1;i<=n;i++){
        if (A[i][s]) v.push_back(i);
    }
    printf ("Le voisinage entrant du sommet %2d est [",s);
    for (int i=0;i<  static_cast<int>(v.size());i++)
        if (i==(int)v.size()-1)
            printf ("%d]\n",v[i]);
        else printf("%d,",v[i]);
    if (v.size()==0){
        printf ("]\n");
    }
}
void voisinage (){
    int s;
    printf ("Enter the summet: ");
    scanf("%d",&s);
    if (directed){
        voisinageSortant(s);
        voisinageEntrant(s);
    }
    vector<int> v;
    for (int i=1;i<=n;i++){
        if (A[s][i] or A[i][s]) v.push_back(i);
    }
    printf ("Le voisinage du sommet %2d est [",s);
    for (int i=0;i<  static_cast<int>(v.size());i++)
        if (i==(int)v.size()-1)
            printf ("%d]\n",v[i]);
        else printf("%d,",v[i]);
}
bool isSimple(){
    //A simple graph is a graph which contains no loops and no parallel arcs
    bool simple=true;
    //We verify that there's no loops
    for (int i=1;i<=n;i++)
        if (A[i][i]) simple=false;
    return simple;
}
bool isComplete(){
    return isSimple() && (m==(n*(n-1))/2);
}
bool isConnexe(){
    bool connexe=true;
    memset(visited,0,sizeof visited);
    queue<int> q;
    q.push (1);
    while (!q.empty()){
        int node=q.front();
        q.pop();
        visited[node]=1;
        for (int i=1;i<=n;i++){
            if (!visited[i] && A[node][i])
                q.push(i);
        }
    }
    for (int i=1;i<=n;i++)
        if (!visited[i]) connexe=false;
    return connexe;
}
bool isHamiltonian(){
    return false;
}
bool isEulerian (){

    if (directed){
        for(int i=1;i<=n;i++)
            if (!(outDegree(i)==inDegree(i)))return false ;
    }
    else {
        for (int i=1;i<=n;i++)
            if (countDegree(i)%2) return false;
    }
    return true;
}
void properties(){
    printf ("Graph A is ");
    if (!directed) printf ("not ");
    printf ("directed, ");
    if (!isSimple()) printf ("not ");
    printf ("simple, ");
    if (!isComplete()) printf ("not ");
    printf ("complete, ");
    if (!isEulerian()) printf ("not ");
    printf ("Eulerian, ");
    if (!isHamiltonian()) printf ("not ");
    printf ("hamiltonian and ");
    if (!isConnexe()) printf ("not ");
    if (!isConnexe() && directed ) printf ("forcefully ");
    printf ("connexe\n");
}
void dfs (int node){
    connected.push_back(node);
    visited[node]=1;
    for (int i=1;i<=n;i++)
        if (!visited[i] && A[node][i])
            dfs(i);
}
void bfs (int source){
    queue<int> q;
    q.push (source);
    while (!q.empty()){
        int node=q.front();
        q.pop();
        if (!visited[node])
            connected.push_back(node);
        visited[node]=1;
        for (int i=1;i<=n;i++){
            if (!visited[i] && A[node][i])
                q.push(i);
        }
    }
}
void parcoursProfondeurGraphe(){
    memset(visited,0,sizeof visited);
    int nbr=0;
    for (int i=1;i<=n;i++){
        if (!visited[i]){
            connected.clear();
            nbr++;
            dfs(i);
            printf ("The elements of %d composant connexe : ",nbr);
            for (int j=0; j< static_cast<int>(connected.size());j++)
                printf ("%2d ",connected[j]);
            puts("");
        }
    }
}
void parcoursLargeurGraphe(){
    memset(visited,0,sizeof visited);
    int nbr=0;
    for (int i=1;i<=n;i++){
        if (!visited[i]){
            connected.clear();
            nbr++;
            bfs(i);
            printf ("les elements du %d composant connexe : ",nbr);
            for (int j=0;j< static_cast<int>(connected.size());j++)
                printf ("%2d ",connected[j]);
            puts("");
        }
    }
}
int main (){
    readGraph();
    displayGraph();
    order();
    numberOfLinks();
    density();
    degree();
    voisinage();
    properties();
    parcoursProfondeurGraphe();
    parcoursLargeurGraphe();
}