Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector < int > G[100005], rev[100005], dag[100005], order;
- int N, M;
- int A[100005], B[100005];
- bool flag[100005] = {};
- int cmp[100005];
- int cnt[100005] = {};
- void dfs(int v)
- {
- if(flag[v]) return;
- flag[v] = true;
- for(int i = 0; i < G[v].size(); i++) dfs(G[v][i]);
- order.push_back(v);
- return;
- }
- void rdfs(int v, int k)
- {
- if(~cmp[v]) return;
- cmp[v] = k;
- for(int i = 0; i < rev[v].size(); i++) rdfs(rev[v][i], k);
- return;
- }
- int main()
- {
- cin >> N >> M;
- for(int i = 0; i < M; i++) {
- cin >> A[i] >> B[i]; --A[i], --B[i];
- G[A[i]].push_back(B[i]);
- rev[B[i]].push_back(A[i]);
- }
- for(int i = 0; i < N; i++) dfs(i);
- int n = 0;
- fill_n(cmp, 100005, -1);
- for(int i = N - 1; i >= 0; i--) {
- if(!~cmp[order[i]]) {
- rdfs(order[i], n); n++;
- }
- }
- for(int i = 0; i < M; i++) if(cmp[A[i]] != cmp[B[i]]) cnt[cmp[B[i]]]++;
- int ans = 0;
- for(int i = 0; i < n; i++) {
- if(cnt[i] == 0) ans++;
- }
- cout << ans << endl;
- return (0);
- }
Add Comment
Please, Sign In to add comment