Submission #733496

#	Time	Username	Problem	Language	Result	Execution time	Memory
733496		rahulverma	Ronald (COCI17_ronald)	Java	120 / 120	814 ms	24148 KiB

ronald

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

class ronald{
	public static int n;
	public static int m;
	public static int[][] graph;
	public static int[] seen;
	public static ArrayList<ArrayList<Integer>> ccs = new ArrayList<>();
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		m = s.nextInt();
		graph = new int[n][n];
		seen = new int[n];
		for(int i = 0; i < m; i++) {
			int v1 = s.nextInt() - 1;
			int v2 = s.nextInt() - 1;
			graph[v1][v2] = 1;
			graph[v2][v1] = 1;
		}
		int c = 0;
		for(int i = 0; i < n; i++) {
			if(seen[i] == 0) {
				ccs.add(new ArrayList<Integer>());
				dfs(i, c);
				c++;
			}
		}
		if(c > 2) {
			System.out.println("NE");
			return;
		}
		boolean works = true;
		for(int i = 0; i < c; i++) {
			boolean w = true;
			for(int node: ccs.get(i)) {
				for(int node2: ccs.get(i)) {
					if(node == node2) continue;
					if(graph[node][node2] == 0) {
						w = false;
						break;
					}
				}
				if(!w) {
					works = false;
					break;
				}
			}
			if(!works) break;
		}
		if(works) System.out.println("DA");
		else System.out.println("NE");
	}
	public static void dfs(int node, int c) {
		seen[node] = 1;
		ccs.get(c).add(node);
		for(int node2 = 0; node2 < n; node2++) {
			if(graph[node][node2] == 1 && seen[node2] == 0) {
				dfs(node2, c);
			}
		}
	}

}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 15 / 15
• Subtask 8: 15 / 15