CAPCITY - Capital City.cpp

#include<bits/stdc++.h>
using namespace std;

int n,e;
vector<int>v1[100005],v2[100005],comp[100005];
bool visited[100005];
int mark;
stack<int>s;


void toposort(int x){

    visited[x]=true;
    //cout<<x<<"\n";

    for(int i=0;i<v1[x].size();i++){

        int xx = v1[x][i];

        if(visited[xx]==false) toposort(xx);

    }

    s.push(x);

    //cout<<"push "<<x<<"\n";

}

void dfs(int x){

    comp[mark].push_back(x);

    //cout<<x<<" ";

    visited[x]=true;

    for(int i=0;i<v2[x].size();i++){

        int xx = v2[x][i];

        if(visited[xx]==false) dfs(xx);

    }

}

void FindScc(){

    //stack<int>emp;

    //swap(s,emp);

    //memset(visited,false,sizeof(visited));

    mark=0;

    for(int i=0;i<=n;i++){

        comp[i].clear();
    }

    //cout<<"here\n";

    for(int i=1;i<=n;i++){

        if(visited[i]==false) toposort(i);

    }

    memset(visited,false,sizeof(visited));

    while(!s.empty()){

        int u = s.top();

        //cout<<u<<"\n";

        s.pop();

        if(visited[u]==false){

            mark++;
            dfs(u);

        }

    }

}

int main(){

    cin>>n>>e;
    int a,b;
    while(e--){

        cin>>a>>b;

        v1[a].push_back(b);
        v2[b].push_back(a);

    }

    FindScc();

    cout<<comp[mark].size()<<"\n";

    sort(comp[mark].begin(),comp[mark].end());

    for(int j=0;j<comp[mark].size();j++){

        cout<<comp[mark][j];
        if(j!=comp[mark].size()-1) cout<<" ";

    }

    cout<<"\n";



}