JAVA Solution Topological sorting based(Kahn's Algorithm)


#1

public class Solution {
public int solve(int A, int[] B, int[] C) {
if(B.length>A)
{
return 0;
}
ArrayList<ArrayList> g=new ArrayList<>();

for(int i=0;i<A;i++)
    {
        g.add(new ArrayList<Integer>());
    }
for(int i=0;i<B.length;i++)
{
    g.get(B[i]-1).add(C[i]-1);
}
int[] in=new int[A];
for(int i=0;i<A;i++)
{
    for(int u:g.get(i))
    {
        in[u]++;
    }
}
Queue<Integer> q=new LinkedList<>();
for(int i=0;i<A;i++)
{
    if(in[i]==0)
    {
        q.add(i);
    }
}
int count=0;
while(!q.isEmpty())
{
    count++;
    int x=q.poll();
    for(int u:g.get(x))
    {
        in[u]--;
        if(in[u]==0)
        {
            //count++;
            q.add(u);
        }
    }
}

return count==A?1:0;
}

}