Advertisement
Guest User

Untitled

a guest
Jun 21st, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,u,t,ne,cost[50001],dp[50001],vis[50001],vis2[50001],id[50001],degin[50001],degout[50001],curcc=0,m,v,cap;
  4. std::vector<int> adj[50004], tranny[50004];
  5. set<int> adj2[50004];
  6. stack<int> order;
  7. set<int> cc;
  8. void dfs(int cur) {
  9. vis[cur] = 1;
  10. for(int i = 0; i<adj[cur].size(); i++){
  11. int child = adj[cur][i];
  12. if(!vis[child]) dfs(child);
  13. }
  14. order.push(cur);
  15. }
  16. void dfstrans(int cur) {
  17. vis2[cur] = 1;
  18. for(int i = 0; i<tranny[cur].size(); i++){
  19. int child = tranny[cur][i];
  20. if(!vis2[child]) dfstrans(child);
  21. }
  22. cc.insert(cur);
  23. }
  24.  
  25. int main(){
  26. t = 1;
  27. int tc = 0;
  28. while (t--) {
  29. curcc = 0;
  30. std::cin >> n >> m >> cap;
  31. cap--;
  32. for(int i = 0; i<m; i++){
  33. std::cin >> u >> v;
  34. --u;--v;
  35. adj[u].push_back(v);
  36. tranny[v].push_back(u);
  37. }
  38.  
  39.  
  40. for(int i = 0; i<n; i++){
  41. if(!vis[i]) {
  42. dfs(i);
  43. }
  44. }
  45. while (!order.empty()) {
  46. int v = order.top(), curcost = 0;
  47. order.pop();
  48. if(vis2[v]) continue;
  49. dfstrans(v);
  50. set<int> in, out;
  51. set<int>::iterator it = cc.begin();
  52. for(;it!=cc.end();it++){
  53. int e = *it;
  54. id[e] = curcc;
  55. }
  56. curcc++;
  57. cc.clear();
  58. }
  59.  
  60. for(int i = 0; i<n; i++){
  61. for(int j = 0; j<adj[i].size(); j++){
  62. int child = adj[i][j];
  63. if(id[i]==id[child]) continue;
  64. adj2[id[i]].insert(id[child]);
  65. degin[id[child]]++;
  66. degout[id[i]]++;
  67. }
  68. }
  69. // printf("curcc = %d\n", curcc);
  70. // for(int i = 0; i<curcc; i++){
  71. // printf("node = %d: ", i);
  72. // for(int e: adj2[i]) printf("%d, ", e);
  73. // printf("\n");
  74. // }
  75.  
  76. int ans = 0;
  77. int capid = id[cap];
  78.  
  79. for(int i = 0; i<curcc; i++){
  80. if(!degin[i] && i!= capid) ans++;
  81. }
  82. // if(degout[capid]==0) ans++;
  83. std::cout << ans << '\n';
  84. }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement