Advertisement
Josif_tepe

Untitled

Jun 1st, 2022
743
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None
  1. #include <iostream>
  2. //#include <bits/stdc++.h>
  3. #include <stack>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7. vector<int>graph[5005];
  8. vector<int>rev_graph[5005];
  9. bool visited[5005];
  10.  
  11. stack<int>s;
  12.  
  13. int najgolem=-2e9;
  14. int najmal=2e9;
  15. int brojac1=0;
  16.  
  17. void dfs(int node){
  18. visited[node]=true;
  19. for(int i=0; i<graph[node].size(); i++){
  20.     int sosed=graph[node][i];
  21.     if(!visited[sosed]){
  22.         dfs(sosed);
  23.     }
  24. }
  25. s.push(node);
  26. }
  27. void rev_dfs(int node){
  28. visited[node]=true;
  29. brojac1+=1;
  30. for(int i=0; i<rev_graph[node].size(); i++){
  31.     int rev_sosed=rev_graph[node][i];
  32.     if(!visited[rev_sosed]){
  33.         rev_dfs(rev_sosed);
  34.     }
  35. }
  36. }
  37. int main()
  38. {
  39.     int brojac=0;
  40.  
  41.     int p, t;
  42.     cin>>p>>t;
  43.     memset(visited, false, sizeof visited);
  44.     for(int i=0; i<t; i++){
  45.         int a, b;
  46.         cin>>a>>b;
  47.         graph[a].push_back(b);
  48.         rev_graph[b].push_back(a);
  49.     }
  50.     for(int i=1; i<=p; i++){
  51.         if(!visited[i]){
  52.             dfs(i);
  53.         }
  54.     }
  55.     memset(visited, false, sizeof visited);
  56.  
  57.     while(!s.empty()){
  58.         int node=s.top();
  59.         if(!visited[node]){
  60.             rev_dfs(node);
  61. //            cout << brojac1 << endl;
  62.             if(najgolem<brojac1){
  63.                 najgolem=brojac1;
  64.             }
  65.             if(najmal>brojac1){
  66.                 najmal=brojac1;
  67.             }
  68.             brojac1=0;
  69.             brojac+=1;
  70.         }
  71.         s.pop();
  72.     }
  73.  
  74.     cout<<brojac<<endl;
  75.     cout<<najmal<<" "<<najgolem;
  76.     return 0;
  77. }
  78.  
Advertisement
RAW Paste Data Copied
Advertisement