結果

問題 No.1610 She Loves Me, She Loves Me Not, ...
ユーザー merlinmerlin
提出日時 2021-07-21 22:32:57
言語 Java21
(openjdk 21)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 1,394 bytes
コンパイル時間 3,861 ms
コンパイル使用メモリ 74,904 KB
実行使用メモリ 55,448 KB
最終ジャッジ日時 2023-09-24 18:46:00
合計ジャッジ時間 8,004 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
49,136 KB
testcase_01 AC 48 ms
49,592 KB
testcase_02 AC 44 ms
49,496 KB
testcase_03 AC 45 ms
49,300 KB
testcase_04 AC 44 ms
49,276 KB
testcase_05 AC 121 ms
55,440 KB
testcase_06 AC 131 ms
54,988 KB
testcase_07 AC 127 ms
55,296 KB
testcase_08 AC 115 ms
55,168 KB
testcase_09 AC 118 ms
54,944 KB
testcase_10 AC 127 ms
53,424 KB
testcase_11 AC 127 ms
55,004 KB
testcase_12 AC 130 ms
54,976 KB
testcase_13 AC 118 ms
55,448 KB
testcase_14 AC 58 ms
49,352 KB
testcase_15 AC 58 ms
49,316 KB
testcase_16 AC 57 ms
50,284 KB
testcase_17 AC 60 ms
49,828 KB
testcase_18 AC 58 ms
49,752 KB
testcase_19 AC 58 ms
49,236 KB
testcase_20 AC 58 ms
50,132 KB
testcase_21 AC 59 ms
49,504 KB
testcase_22 AC 57 ms
49,608 KB
testcase_23 AC 44 ms
49,136 KB
testcase_24 AC 44 ms
49,124 KB
testcase_25 AC 44 ms
49,272 KB
testcase_26 AC 44 ms
49,276 KB
testcase_27 AC 45 ms
49,740 KB
testcase_28 AC 45 ms
49,276 KB
testcase_29 AC 44 ms
49,280 KB
testcase_30 AC 46 ms
49,676 KB
testcase_31 AC 44 ms
49,272 KB
testcase_32 AC 43 ms
49,124 KB
testcase_33 AC 44 ms
49,272 KB
testcase_34 AC 44 ms
49,300 KB
testcase_35 AC 44 ms
49,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();

        String s[]=bu.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
        ArrayList<Integer> g[]=new ArrayList[n];
        int i,l[]=new int[n],d[]=new int[n];
        for(i=0;i<n;i++) g[i]=new ArrayList<>();
        for(i=0;i<m;i++)
        {
            s=bu.readLine().split(" ");
            int u=Integer.parseInt(s[0])-1,v=Integer.parseInt(s[1])-1;
            g[u].add(v); g[v].add(u);
        }

        time=0; bridge=0;
        boolean vis[]=new boolean[n];
        for(i=0;i<n;i++)
        if(!vis[i]) dfs(g,l,d,vis,i,-1);
        //System.out.println(bridge);
        if(bridge%2==0) sb.append("No");
        else sb.append("Yes");
        System.out.println(sb);
    }

    static int time,bridge;
    static void dfs(ArrayList<Integer> g[],int l[],int d[],boolean vis[],int n,int p)
    {
        l[n]=d[n]=++time;
        //System.out.println(n);
        vis[n]=true;
        for(int x:g[n])
        if(!vis[x])
        {
            dfs(g,l,d,vis,x,n);
            l[n]=Math.min(l[n],l[x]);
            if(l[x]>d[n]) bridge++;
        }
        else if(x!=p) l[n]=Math.min(l[n],d[x]);
    }
}
0