Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Solver {
- public:
- void init(istream &is);
- void solve();
- void print(ostream &os);
- private:
- void firstStep();
- void secondStep();
- void thirdStep();
- void dfs(int v);
- void dfs2(int v);
- void dfs3(int v);
- void dfs4(int v);
- int n, m, answer;
- int count;
- vector < vector <int> > edges;
- vector < vector <int> > edgesT;
- vector <int> f;
- vector <char> isAvaliable;
- };
- void Solver::init(istream &is) {
- is >> n >> m;
- edges.assign(n, vector <int> ());
- edgesT.assign(n, vector <int> ());
- int a, b;
- for (int i = 0; i < m; ++i) {
- cin >> a >> b;
- edges[a - 1].push_back(b - 1);
- edgesT[b - 1].push_back(a - 1);
- }
- isAvaliable.assign(n, 0);
- count = 0;
- answer = 0;
- }
- void Solver::dfs(int v) {
- count++;
- isAvaliable[v] = 1;
- for (int i = 0; i < edges[v].size(); ++i)
- dfs(edges[v][i]);
- }
- void Solver::dfs2(int v) {
- if (isAvaliable[v] == 1)
- return;
- count++;
- isAvaliable[v] = 1;
- for (int i = 0; i < edges[v].size(); ++i)
- dfs2(edges[v][i]);
- }
- void Solver::dfs3(int v) {
- isAvaliable[v] = 2;
- for (int i = 0; i < edges[v].size(); ++i)
- if (isAvaliable[edges[v][i]] == 0)
- dfs3(edges[v][i]);
- f.push_back(v);
- }
- void Solver::dfs4(int v) {
- isAvaliable[v] = 2;
- for (int i = 0; i < edgesT[v].size(); ++i)
- if (isAvaliable[edgesT[v][i]] == 0)
- dfs4(edgesT[v][i]);
- }
- void Solver::solve() {
- firstStep();
- secondStep();
- thirdStep();
- }
- void Solver::firstStep() {
- dfs(0);
- }
- void Solver::secondStep() {
- if (count != n) {
- for (int i = 0; i < n; ++i)
- if (isAvaliable[i] == 0 && edgesT[i].empty()) {
- dfs2(i);
- answer++;
- }
- }
- }
- void Solver::thirdStep() {
- if (count != n) {
- for (int i = 0; i < n; ++i)
- if (isAvaliable[i] == 0)
- dfs3(i);
- for (int i = 0; i < n; ++i)
- if (isAvaliable[i] == 2)
- isAvaliable[i] = 0;
- int last_f = f.size() - 1;
- for (last_f; last_f >= 0; --last_f)
- if (isAvaliable[f[last_f]] == 0) {
- dfs4(f[last_f]);
- answer++;
- }
- }
- }
- void Solver::print(ostream &os) {
- os << answer;
- }
- int main() {
- Solver s;
- s.init(std::cin);
- s.solve();
- s.print(std::cout);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement