CSES 1682 Flight Routes Check
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
vector< vector<int> > net(MAXN),netr(MAXN);
void goDFS(int start, set<int>& rset, vector< vector<int> >& lnet){
? ? vector<bool> vis(MAXN);
? ? stack<int> s;
? ? s.push(start);
? ? int a;
? ? while(!s.empty()){
? ? ? ? a=s.top();
? ? ? ? rset.insert(a);
? ? ? ? s.pop();
? ? ? ? for(int b :lnet[a]){
? ? ? ? ? ? if(!vis[b]){
? ? ? ? ? ? ? ? s.push(b);
? ? ? ? ? ? ? ? vis[b]=true;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main()
{
? ? int n,m;
? ? cin>>n>>m;
? ? for(int i=1;i<=m;i++){
? ? ? ? int a,b;
? ? ? ? cin>>a>>b;
? ? ? ? net[a].push_back(b);
? ? ? ? netr[b].push_back(a);
? ? }
? ? set<int> whole,ndfs,ndfsr,r1;
? ? for(int i=1;i<=n;i++) whole.insert(i);
? ? goDFS(1,ndfs,net);
? ? goDFS(1,ndfsr,netr);
? ? int sizenet=ndfs.size();
? ? int sizenetr=ndfsr.size();
? ? if(sizenet==n && sizenetr==n){
? ? ? ? cout<<"YES"<<endl;
? ? }else{
? ? ? ? cout<<"NO"<<endl;
? ? ? ? if(sizenet<n){
? ? ? ? ? ? set_difference(whole.begin(),whole.end(),ndfs.begin(),ndfs.end(),inserter(r1,r1.begin()));
? ? ? ? ? ? cout<<1<<" "<<*r1.begin()<<endl;
? ? ? ? }else{
? ? ? ? ? ? set_difference(whole.begin(),whole.end(),ndfsr.begin(),ndfsr.end(),inserter(r1,r1.begin()));
? ? ? ? ? ? cout<<*r1.begin()<<" "<<1<<endl;
? ? ? ? }
? ? }? ??
? ? return 0;
}