結果

問題 No.1610 She Loves Me, She Loves Me Not, ...
ユーザー merlinmerlin
提出日時 2021-07-21 22:32:57
言語 Java
(openjdk 23)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 1,394 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 78,984 KB
実行使用メモリ 56,748 KB
最終ジャッジ日時 2024-07-17 19:32:00
合計ジャッジ時間 6,734 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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