---
title: 802. Find Eventual Safe States
tags: graph
description: share source code.
---

# 802. Find Eventual Safe States

class Solution {
    
    // -1 未 visited, 0 no cycle, 1 cycle
    public List<Integer> eventualSafeNodes(int[][] graph) {
            int n = graph.length;
            int [] color = new int [n + 1];
        
            List<Integer> list = new ArrayList<>();
        
            for(int i = 0; i < n; i ++){
                Arrays.fill(color, -1);
                
                if(hasCycle(graph, i, color)){
                    list.add(i);
                }
            } 
        
            return list;
    }
    
    public boolean hasCycle(int[][] graph, int u, int [] color){
           if(color[u] != -1){
               return color[u] == 0;
           }
        
           color[u] = 1;
        
           for(int v : graph[u]){
               if(!hasCycle(graph, v, color)){
                   return false;
               };
           }
        
           color[u] = 0;
        
           return true;
           
    }
}