Graph

import java.io.*;
import java.util.*;
import java.util.LinkedList;

class Graph
{
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v,int w)
    {
        if (!adj[v].contains(w))
                adj[v].add(w);
        if (!adj[w].contains(v))
            adj[w].add(v);
    }

    boolean greedyColoring(int resultEdge)
    {
        int result[] = new int[V];

        Arrays.fill(result, -1);

        result[0] = 0;

        boolean available[] = new boolean[V];

        Arrays.fill(available, true);

        for (int u = 1; u < V; u++)
        {
            Iterator<Integer> it = adj[u].iterator() ;
            while (it.hasNext())
            {
                int i = it.next();
                if (result[i] != -1)
                    available[result[i]] = false;
            }

            int cr;
            for (cr = 0; cr < V; cr++){
                if (available[cr])
                    break;
            }

            result[u] = cr;
            Arrays.fill(available, true);
        }

        boolean flag = true;
        for (int u = 0; u < V; u++) {
            if(result[u] >=3){
                flag = false;
            }
        }

        if (flag){
            String outputFileName = "file1.txt";

            try (BufferedWriter writter = new BufferedWriter(new FileWriter(outputFileName))) {
                writter.write("1000,"+resultEdge+",colorFirst,colorSecond\n");
                for (int i = 0; i < 1000; i++){
                    for (int j = 0; j < adj[i].size(); j++){
                        writter.write(i+ "," +adj[i].get(j)+","+result[i]+","+result[adj[i].get(j)]);
                        writter.write("\n");
                    }
                }
            }
            catch (IOException e) {
                e.printStackTrace();
            }

        }
        return flag;
    }

    public static void main(String args[])
    {
        int n = 1000;
        Random rnd = new Random();
        boolean result;
        int resultEdge = 0;
        int iteration = 0;
        do {
            iteration++;

            if(iteration % 1000 == 0)
                System.out.println("iteration "+iteration/1000+"K");
            resultEdge = 0;
            Graph g1 = new Graph(n);

            for (int i = 0; i < n; i++) {
                int countNeigh = rnd.nextInt(8) + 1;
                for (int j = 1; j <= countNeigh; j++) {
                    if(i+1 == n) break;
                    int Neigh;
                    do {
                        Neigh = rnd.nextInt(n) ;

                    } while (i >= Neigh);

                    if(g1.adj[i].size()+1 < 8)
                        if(g1.adj[Neigh].size()+1 < 3){
                            resultEdge++;
                            g1.addEdge(i, Neigh);
                        }

                }
            }
            result = g1.greedyColoring(resultEdge);
        }while(!result);
        System.out.println(result);
        System.out.println("result edge = " + resultEdge);

    }
}