CSES - Shared codeLink to this code:
https://cses.fi/paste/5568c4710c3ac705686e17/
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
class FlightRoutesCheck{
vector<int>*graph,*flipGraph;
vector<bool>vis;
vector<int>ans,group;
stack<int>st;
public:
FlightRoutesCheck(vector<int> *g,vector<int>*f,int n){
graph=g;
flipGraph=f;
vis.resize(n+1,false);
group.resize(n+1,0);
}
void traverse(int u){
if(vis[u])return;
vis[u]=true;
for(int v:graph[u]){
traverse(v);
}
st.push(u);
}
void revTraverse(int u,int &g){
if(vis[u])return;
group[u]=g;
vis[u]=true;
for(int v:flipGraph[u]){
revTraverse(v,g);
}
}
vector<int> getSol(int n){
for(int i=1;i<=n;i++){
if(!vis[i]){
traverse(i);
}
}
fill(vis.begin(),vis.end(),false);
int num,cnt=1;
while(!st.empty()){
num=st.top();
st.pop();
if(!vis[num]){
revTraverse(num,cnt);
cnt++;
}
}
group[0]=cnt-1;
return group;
}
};
int main(){
int n,m,a,b;
cin>>n>>m;
vector<int> graph[n+1],flipGraph[n+1];
for(int i=0;i<m;i++){
cin>>a>>b;
graph[a].push_back(b);
flipGraph[b].push_back(a);
}
FlightRoutesCheck check(graph,flipGraph,n);
vector<int> ans=check.getSol(n);
cout<<ans[0]<<" "<<endl;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
return 0;
}