/**
 * Created by Mateusz Soliwodzki on 20.02.2017.
 */
import java.util.Stack;


public class Skojarzenie {

    static int V;
    static int E;
    static Stack<Integer> q = new Stack<>();
    static int[][] G;
    static int[] colorArr;
    static int fmax;
    static int[][] C;                          // Macierz przepustowości
    static int[][] F;                          // Macierz przepływów netto
    static int[] P;
    static int[] CFP;

    static boolean isBipartite()
    {

        for (int i=0; i<V; ++i)
            colorArr[i] = 0;

        for(int j = 0; j<V; j++){
            if(colorArr[j] == 0){
                colorArr[j] = 1;
                q.add(j);
                while (q.size() != 0)
                {
                    int u = q.peek();
                    q.pop();
                    for (int v=0; v<V; ++v)
                    {
                        if (G[u][v]== 1 && colorArr[v]==0)
                        {
                            colorArr[v] = -colorArr[u];
                            q.add(v);
                        }
                        else if (G[u][v]== 1 && colorArr[v] == colorArr[u])
                            return false;
                    }
                 }
            }
        }
        return true;
    }

    public static void main(String args[]) {

        V = 10;
        E = 17;
        colorArr = new int[V];
        G = new int[][]{
              // 0  1  2  3  4  5  6  7  8  9
                {0, 0, 1, 1, 1, 0, 0, 0, 1, 0}, //0
                {0, 0, 1, 0, 1, 0, 0, 0, 1, 0}, //1
                {1, 1, 0, 0, 0, 1, 0, 1, 0, 0}, //2
                {1, 0, 0, 0, 0, 0, 0, 1, 0, 1}, //3
                {1, 1, 0, 0, 0, 1, 0, 0, 0, 0}, //4
                {0, 0, 1, 0, 1, 0, 1, 0, 0, 0}, //5
                {0, 0, 0, 0, 0, 1, 0, 1, 0, 1}, //6
                {0, 0, 0, 1, 0, 0, 1, 0, 0, 0}, //7
                {1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, //8
                {0, 0, 0, 1, 1, 0, 1, 0, 1, 0}, //9
        };
        if(isBipartite())
        {
            C = new int [V+2][V+2];            // Macierz przepustowości krawędzi
            F = new int [V+2][V+2];            // Macierz przepływów netto

            for(int i = 0; i <= V + 1; i++)
            {
                C[i] = new int [V+2];
                F[i] = new int [V+2];
                for(int j = 0; j <= V + 1; j++)
                {
                    C[i][j] = 0;
                    F[i][j] = 0;
                }
            }

            // Ustawiamy macierz przepustowości
            for(int i = 0; i < V; i++)
                if(colorArr[i] == -1)
                {
                    for(pr = G[i]; pr; pr = pr -> next) // Przeglądamy listę sąsiadów wierzchołka niebieskiego
                        C[i][pr->data] = 1;     // Przepustowość krawędzi do wierzchołka czerwonego
                    C[V][i] = 1;              // Przepustowość krawędzi od źródła
                }
                else C[i][V+1] = 1;         // Przepustowość krawędzi do ujścia

            //**************************************************
            //** Tutaj rozpoczyna się algorytm Edmondsa-Karpa **
            //**************************************************

            fmax = 0;

            while(true)
            {
                for(int i = 0; i <= V + 1; i++) P[i] = -1;

                P[V] = -2;
                CFP[V] = Integer.MAX_VALUE;

                while(!q.empty()) q.pop();
                q.push(V);

                esc = false;

                while(!q.empty())
                {
                    v = q.peek(); q.pop();

                    for(int u = 0; u <= V + 1; u++)
                    {
                        cp = C[v][u] - F[v][u];
                        if(cp && (P[u] == -1))
                        {
                            P[u] = v;
                            if(CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
                            if(u == V+1)
                            {
                                fmax += CFP[V+1];
                                i = u;
                                while(i != V)
                                {
                                    v = P[i];
                                    F[v][i] += CFP[V+1];
                                    F[i][v] -= CFP[V+1];
                                    i = v;
                                }
                                esc = true; break;
                            }
                            Q.push(u);
                        }
                    }
                    if(esc) break;
                }
                if(!esc) break;
            }

            System.out.println("Liczba skojarzeń : " + fmax);
            if(fmax > 0)
                for(int v = 0; v < V; v++)
                    for(int u = 0; u < V; u++)
                        if((C[v][u] == 1) && (F[v][u] == 1))
                            System.out.println(v + " - "+ u);
        }else
            System.out.println("Graf nie jest dwudzielny");
    }
}