글 읽기 - 반례 찾기 부탁드립니다

jkikd 2년 전 0

check는 초기 무한으로 설정하여 1과 연결되어 감염 되는 경우 1로 값을 지정합니다

이후 1이 아닌 check의 수 는 감염되지 않은 컴퓨터의 수 이며

전체 노드 n에서 감염되지 않은 수를 뺀 값을 감염된 결과로 출력하였습니다

틀렸습니다가 나왔는데 반례찾기 좀 도와주세요

import java.util.*;
public class Main{
    public static int n;
    public static int m;
    public static int[][] map;
    public static int index=1;
    public static int[] check;
    private static int INF = (int)1e9;
    public static int cnt=0;
    
    public static void findwarm(int[][] map){
        check[0] = 1;
        for(int j=1;j<=n;j++){
            for(int i=index;i<=n;i++){
                if(map[j][i]==1 && check[i-1]!=1){
                    if(check[j-1]!=1){
                        check[i-1] = INF;
                    }else{
                        check[i-1]=1;
                    }
                }
            }
            index=1;
        }
        for(int i=0;i<n;i++){
            if(check[i]==INF)
                cnt++;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Graph arrG = new Graph(n);
        map = new int[n+1][n+1];
        check = new int[n];
        Arrays.fill(check, INF);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b = sc.nextInt();
            arrG.put(a,b);
        }
        map = arrG.getGraph();
        findwarm(map);
        System.out.println(n-cnt);
    }
}
class Graph{
    private int[][] arrGraph;
    public Graph(int initSize){
        this.arrGraph = new int[initSize+1][initSize+1];
    }
    public int[][] getGraph(){
        return this.arrGraph;
    }
    public void put(int x, int y){
        arrGraph[x][y] = arrGraph[y][x]=1;
    }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 찾기 부탁드립니다

jkikd 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말