Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class ps6gen {
- public static Random random = new Random();
- static int parent[][];
- static int par_size[];
- static Vector<Vector<Integer>> adj;
- public static void update(int from){
- for (int t = 0; t < adj.get(from).size();t++){
- boolean check = false;
- int to = adj.get(from).get(t);
- for (int y = 0; y < par_size[from];y++){
- if (!contain(to,parent[from][y])){
- parent[to][par_size[to]] = parent[from][y];
- par_size[to]++;
- check = true;
- }
- }
- if (!contain(to,from)){
- parent[to][par_size[to]] = from;
- par_size[to]++;
- check = true;
- }
- if (check == true)
- update(to);
- }
- }
- public static boolean contains(int cur, int next){
- //System.out.println(cur+" "+next);
- if (cur == next)
- return true;
- for (int i = 0; i < par_size[cur]; i++){
- if (contains(parent[cur][i],next))
- return true;
- }
- return false;
- }
- public static boolean contain(int cur, int next){
- for (int i = 0; i < par_size[cur]; i++){
- if (parent[cur][i] == next)
- return true;
- }
- return false;
- }
- public static void main(String args[]){
- int Vcount = 49;
- int Ecount = 70;
- int Wlimit = 9;
- adj = new Vector<Vector<Integer>>();
- for (int a = 0; a < Vcount; a++)
- adj.add(new Vector<Integer>());
- Vector<Integer> spanning = new Vector<Integer>();
- parent = new int[Vcount][];
- par_size = new int[Vcount];
- for (int h = 0; h < Vcount; h++){
- parent[h] = new int[Vcount];
- par_size[h] = 0;
- }
- boolean visited[] = new boolean[Vcount];
- for (int y = 0; y < Vcount; y++)
- visited[y] = false;
- visited[0] = true;
- spanning.add(0);
- int add = 0;
- boolean full = false;
- for (int i = 0; i < Ecount; i++){
- /*
- System.out.println(i+"-----");
- for (int o = 0; o < Vcount; o++ ){
- System.out.println("----->"+o+", "+par_size[o]);
- for (int x = 0; x < par_size[o];x++)
- System.out.printf("%d ", parent[o][x]);
- System.out.println("");
- }
- System.out.println("-----");
- */
- int cur = spanning.get(random.nextInt(spanning.size()));
- int to = random.nextInt(Vcount);
- //System.out.printf("From: %d, To: ",cur);
- while ((cur == to)||contain(cur,to)||
- (adj.get(cur).contains(((Integer)to)))||
- (adj.get(to).contains(((Integer)cur)))){
- cur = spanning.get(random.nextInt(spanning.size()));
- to = random.nextInt(Vcount);
- int ra = random.nextInt(10);
- if (ra < 3)
- to = random.nextInt(Vcount);
- else{
- if (!full){
- boolean found = false;
- for (int w = 0; w < Vcount; w++){
- if (!visited[w]){
- to = w;
- found = true;
- break;
- }
- }
- if (found == false)
- full = true;
- }
- else
- to = random.nextInt(Vcount);
- }
- }
- //System.out.println("Adding edge "+cur+" "+to+", "+par_size[cur]+" "+par_size[to]);
- //System.out.println(to);
- spanning.add(to);
- visited[to] = true;
- adj.get(cur).add(to);
- if (!contain(cur,to)){
- parent[to][par_size[to]] = cur;
- par_size[to]++;
- for (int t = 0; t < par_size[cur]; t++){
- if (!contain(to,parent[cur][t])){
- parent[to][par_size[to]] = parent[cur][t];
- par_size[to]++;
- }
- }
- //System.out.println("Updating "+to);
- update(to);
- }
- if (i == Ecount-1){
- for (int q = 0; q < Vcount; q++){
- if (visited[q] == false){
- i--;
- add++;
- break;
- }
- }
- }
- }
- for (int m = 0; m < Vcount; m++){
- if (adj.get(m).size() == 0){
- adj.get(m).add(Vcount);
- add++;
- }
- }
- System.out.println("1");
- System.out.println("");
- System.out.println((Vcount+1)+" "+(Ecount+add));
- System.out.printf("%d",random.nextInt(Wlimit)+1);
- for (int m = 0; m < Vcount-1; m++)
- System.out.printf(" %d",random.nextInt(Wlimit)+1);
- System.out.println(" 0");
- for (int m = 0; m < Vcount; m++){
- for (int b = 0; b < adj.get(m).size(); b++){
- System.out.println(m+" "+adj.get(m).get(b));
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment