Just Topological Sort


#1

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.

vector<vector<int>> graph;
vector<int> inDegree;
vector<bool> vis;

void calcInDegree(){
    for(int i=0;i<inDegree.size();i++)
        for(int a: graph[i])
            inDegree[a]++;
}

bool findTopoSort(){
    calcInDegree();
    queue<int> q;
    vector<int> topoSort;
    for(int i=0;i<inDegree.size();i++){
        if(inDegree[i]==0)q.push(i);
    }
    while(!q.empty()){
        int temp= q.front();
        q.pop();
        topoSort.push_back(temp);
        for(auto a: graph[temp]){
            if(inDegree[a]>0){
                inDegree[a]--;
                if(inDegree[a]==0)q.push(a);
            }
        }
    }
    return topoSort.size()==inDegree.size(); 
}

int Solution::solve(int n, vector<int> &B, vector<int> &C) {
    graph.clear(), inDegree.clear(), vis.clear();
    graph.resize(n);
    inDegree.resize(n,0);
    vis.resize(n,false);
    for(int i=0;i<B.size();i++){
        graph[B[i]-1].push_back(C[i]-1);
    }
    return findTopoSort();
}