Advertisement
overwater

Untitled

May 2nd, 2015
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Solver {
  6. public:
  7.     void init(istream &is);
  8.     void solve();
  9.     void print(ostream &os);
  10. private:
  11.     void firstStep();
  12.     void secondStep();
  13.     void thirdStep();
  14.  
  15.     void dfs(int v);
  16.     void dfs2(int v);
  17.     void dfs3(int v);
  18.     void dfs4(int v);
  19.  
  20.     int n, m, answer;
  21.     int count;
  22.     vector < vector <int> > edges;
  23.     vector < vector <int> > edgesT;
  24.  
  25.     vector <int> f;
  26.     vector <char> isAvaliable;
  27. };
  28.  
  29. void Solver::init(istream &is) {
  30.     is >> n >> m;
  31.     edges.assign(n, vector <int> ());
  32.     edgesT.assign(n, vector <int> ());
  33.  
  34.     int a, b;
  35.     for (int i = 0; i < m; ++i) {
  36.         cin >> a >> b;
  37.         edges[a - 1].push_back(b - 1);
  38.         edgesT[b - 1].push_back(a - 1);
  39.     }
  40.  
  41.     isAvaliable.assign(n, 0);
  42.     count = 0;
  43.     answer = 0;
  44. }
  45.  
  46. void Solver::dfs(int v) {
  47.     count++;
  48.     isAvaliable[v] = 1;
  49.     for (int i = 0; i < edges[v].size(); ++i)
  50.         dfs(edges[v][i]);
  51. }
  52.  
  53. void Solver::dfs2(int v) {
  54.     if (isAvaliable[v] == 1)
  55.         return;
  56.     count++;
  57.     isAvaliable[v] = 1;
  58.     for (int i = 0; i < edges[v].size(); ++i)
  59.         dfs2(edges[v][i]);
  60. }
  61.  
  62. void Solver::dfs3(int v) {
  63.     isAvaliable[v] = 2;
  64.     for (int i = 0; i < edges[v].size(); ++i)
  65.     if (isAvaliable[edges[v][i]] == 0)
  66.         dfs3(edges[v][i]);
  67.  
  68.     f.push_back(v);
  69. }
  70.  
  71. void Solver::dfs4(int v) {
  72.     isAvaliable[v] = 2;
  73.     for (int i = 0; i < edgesT[v].size(); ++i)
  74.     if (isAvaliable[edgesT[v][i]] == 0)
  75.         dfs4(edgesT[v][i]);
  76. }
  77.  
  78.  
  79. void Solver::solve() {
  80.     firstStep();
  81.     secondStep();
  82.     thirdStep();
  83. }
  84.  
  85. void Solver::firstStep() {
  86.     dfs(0);
  87. }
  88.  
  89. void Solver::secondStep() {
  90.     if (count != n) {
  91.     for (int i = 0; i < n; ++i)
  92.         if (isAvaliable[i] == 0 && edgesT[i].empty()) {
  93.             dfs2(i);
  94.             answer++;
  95.         }
  96.     }
  97. }
  98.  
  99. void Solver::thirdStep() {
  100.     if (count != n) {
  101.     for (int i = 0; i < n; ++i)
  102.         if (isAvaliable[i] == 0)
  103.             dfs3(i);
  104.  
  105.     for (int i = 0; i < n; ++i)
  106.         if (isAvaliable[i] == 2)
  107.             isAvaliable[i] = 0;
  108.         int last_f = f.size() - 1;
  109.         for (last_f; last_f >= 0; --last_f)
  110.             if (isAvaliable[f[last_f]] == 0) {
  111.                 dfs4(f[last_f]);
  112.                 answer++;
  113.         }
  114.     }
  115. }
  116.  
  117. void Solver::print(ostream &os) {
  118.     os << answer;
  119. }
  120.  
  121. int main() {
  122.     Solver s;
  123.  
  124.     s.init(std::cin);
  125.     s.solve();
  126.     s.print(std::cout);
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement