ash_sinha

Untitled

Nov 2nd, 2022
1,009
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dfs(int node,int p,vector<vector<int>> &g){
  5.     int ans=1;
  6.     for(auto x:g[node]) {
  7.         if(x!=p) ans+=dfs(x,node,g);
  8.     }
  9.     return ans;
  10. }
  11. int main()
  12. {
  13.     int n,m;
  14.     cin>>n>>m;
  15.     vector<vector<int>> g(n+1);
  16.     vector<int> prim(m),dep,indegree(n+1,0);
  17.     vector<vector<int>> edge;
  18.     set<vector<int>> st_edge;
  19.     for(int i=0;i<m;i++) cin>>prim[i];
  20.     cin>>m;dep.resize(m);
  21.     for(int i=0;i<m;i++) cin>>dep[i];
  22.     for(int i=0;i<min(dep.size(),prim.size());i++){
  23.         g[prim[i]].push_back(dep[i]);
  24.         indegree[dep[i]]++;
  25.         edge.push_back({prim[i],dep[i]});
  26.         st_edge.insert({prim[i],dep[i]});
  27.     }
  28.     int ans=0;
  29.     vector<int> vis(n+1,0);
  30.     queue<int> q;
  31.     for(int i=1;i<=n;i++) if(indegree[i]==0) q.push(i);
  32.     while(!q.empty()){
  33.         int temp=q.front();q.pop();
  34.         ans++;
  35.         vis[temp]=1;
  36.         for(auto x:g[temp]){
  37.             indegree[x]--;
  38.             if(indegree[x]==0) q.push(x);
  39.         }
  40.     }
  41.     for(auto x:edge){
  42.         int n1=x[0],n2=x[1];
  43.         if(vis[n1]==0 && vis[n2]==0 && st_edge.find({n2,n1})!=st_edge.end()){
  44.             int temp = max(dfs(n1,n2,g),dfs(n2,n1,g));
  45.             ans+=temp;
  46.             vis[n1]=1;
  47.             vis[n2]=1;
  48.         }
  49.     }
  50.     cout<<ans<<"\n";
  51.  
  52. }
Advertisement
Add Comment
Please, Sign In to add comment