Using disjoint set

programming
Tags: #<Tag:0x00007f24354972c0>

#1
int find(int u, vector<int> &parent){
    if(parent[u]==-1) return u;
    return parent[u]=find(parent[u],parent);
}

int Solution::solve(int A, vector<int> &B, vector<int> &C) {
    if(A==1) return 1;
    vector<int> parent(A+1,-1);
    for(int i=0;i<B.size();i++){
        int course = B[i]; int prereq = C[i];
        if(find(course,parent)==find(prereq,parent)){
            return 0;
        }
        parent[course]=prereq;
    }
    return 1;
}

#2

hey this solution is being accepted but it is not correct
try
1->3->4->5->1->2
5
5 1 3 4 1 5
5 3 4 5 2 1
your code gives 1 but the expected is 0.
i wasted a lot of time thinking how this is correct


#3

How can some course be a prerequisite of itself :\