Please read the new rule regarding the restriction on the use of AI tools. ×

vidhansharma01's blog

By vidhansharma01, history, 2 years ago, In English

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

public class DsuGraph {

public static void main(String args[]){
    InputReader in = new InputReader();
    PrintWriter out = new PrintWriter(System.out);
    Task solver = new Task();
    solver.solve(1, in, out);
    out.close();
}
static int mod = (int)1e9+7;

static class Task{

    static class Subset{
        int parent, size;
    }

    static class Pair{
        int x, y;
        public Pair(int x, int y){this.x=x; this.y = y;}
    }

    public void solve(int T, InputReader in, PrintWriter out) {
        int N = in.nextInt();
        adj = new ArrayList[N];
        subset = new Subset[N];
        for (int i =  0 ; i< N; i++){
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++){
            subset[i] = new Subset();
            subset[i].parent = i;
            subset[i].size = 1;
        }

        List<Pair> list = new ArrayList<>();
        int M = N-1;
        while (M-- > 0){
            int x = in.nextInt()-1;
            int y = in.nextInt()-1;

            if(union(x, y)){

            }else{
                list.add(new Pair(x, y));
            }
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0 ;i < N; i++){
            if (!set.contains(root(i))){
                set.add(root(i));
            }
        }

        out.println(set.size()-1);

        int p = set.pollFirst();
        for (int i = 0 ; i< list.size(); i++){
            int x = set.pollFirst();
            out.println((list.get(i).x+1) + " " + (list.get(i).y+1) + " " + (p+1) + " " +  (x+1) );
        }
    }

    private boolean union(int u, int v) {
        int r1 = root(u);
        int r2 = root(v);

        if (r1 == r2)
            return false;

        if (r1 != r2){
            if (subset[r1].size > subset[r2].size){
                subset[r2].parent = r1;
                subset[r1].size += subset[r2].size;
            }else{
                subset[r1].parent = r2;
                subset[r2].size += subset[r1].size;
            }
        }
        return true;
    }

    private int root(int v) {
        if (subset[v].parent != v)
            subset[v].parent = root(subset[v].parent);
        return subset[v].parent;
    }

    static boolean visited[];
    static int parent[];
    static List<Integer> adj[];
    static Subset subset[];

}

static class InputReader {
    BufferedReader br;
    StringTokenizer st;
    public InputReader() {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

}

Full text and comments »

  • Vote: I like it
  • -20
  • Vote: I do not like it