Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n,u,t,ne,cost[50001],dp[50001],vis[50001],vis2[50001],id[50001],degin[50001],degout[50001],curcc=0,m,v,cap;
- std::vector<int> adj[50004], tranny[50004];
- set<int> adj2[50004];
- stack<int> order;
- set<int> cc;
- void dfs(int cur) {
- vis[cur] = 1;
- for(int i = 0; i<adj[cur].size(); i++){
- int child = adj[cur][i];
- if(!vis[child]) dfs(child);
- }
- order.push(cur);
- }
- void dfstrans(int cur) {
- vis2[cur] = 1;
- for(int i = 0; i<tranny[cur].size(); i++){
- int child = tranny[cur][i];
- if(!vis2[child]) dfstrans(child);
- }
- cc.insert(cur);
- }
- int main(){
- t = 1;
- int tc = 0;
- while (t--) {
- curcc = 0;
- std::cin >> n >> m >> cap;
- cap--;
- for(int i = 0; i<m; i++){
- std::cin >> u >> v;
- --u;--v;
- adj[u].push_back(v);
- tranny[v].push_back(u);
- }
- for(int i = 0; i<n; i++){
- if(!vis[i]) {
- dfs(i);
- }
- }
- while (!order.empty()) {
- int v = order.top(), curcost = 0;
- order.pop();
- if(vis2[v]) continue;
- dfstrans(v);
- set<int> in, out;
- set<int>::iterator it = cc.begin();
- for(;it!=cc.end();it++){
- int e = *it;
- id[e] = curcc;
- }
- curcc++;
- cc.clear();
- }
- for(int i = 0; i<n; i++){
- for(int j = 0; j<adj[i].size(); j++){
- int child = adj[i][j];
- if(id[i]==id[child]) continue;
- adj2[id[i]].insert(id[child]);
- degin[id[child]]++;
- degout[id[i]]++;
- }
- }
- // printf("curcc = %d\n", curcc);
- // for(int i = 0; i<curcc; i++){
- // printf("node = %d: ", i);
- // for(int e: adj2[i]) printf("%d, ", e);
- // printf("\n");
- // }
- int ans = 0;
- int capid = id[cap];
- for(int i = 0; i<curcc; i++){
- if(!degin[i] && i!= capid) ans++;
- }
- // if(degout[capid]==0) ans++;
- std::cout << ans << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement