Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n,m;
  5. bool con1[1005][1005] = {false};
  6. bool con2[21005][1005] = {false};
  7. bool vis[1005] = {false};
  8. vector<int> dep[1005];
  9.  
  10.  
  11. int iscon1(int x,int y){
  12. if(con1[x][y]==true) return 1;
  13. for(int i = 0;i < dep[x].size();i++){
  14. if(vis[dep[x][i]]==false){
  15. vis[dep[x][i]] = true;
  16. if(iscon1(dep[x][i],y)==1)
  17. return 1;
  18. }
  19.  
  20. }
  21. return 0;
  22. }
  23.  
  24. int iscon2(int x,int y){
  25. if(con2[y][x]==true) return 1;
  26. for(int i = 0;i < dep[x].size();i++){
  27. if(vis[dep[x][i]]==false){
  28. vis[dep[x][i]] = true;
  29. if(iscon2(dep[x][i],y)==1)
  30. return 1;
  31. }
  32.  
  33. }
  34. return 0;
  35. }
  36.  
  37.  
  38.  
  39.  
  40. int main(){
  41. int a,b,ans = 0;
  42. scanf("%d%d",&n,&m);
  43. for(int i = 0;i < m;i++){
  44. scanf("%d%d",&a,&b);
  45. dep[a].push_back(b);
  46. }
  47. for(int i = 1;i <= n;i++){
  48. con1[i][i] = con2[i][i] = true;
  49. }
  50. for(int i = 1;i <= n;i++){
  51. for(int j = 1;j <= n;j++){
  52. if(iscon1(i,j)==1){
  53. fill(vis,vis+1005,false);
  54. con1[i][j] = true;
  55. }
  56. else if(iscon2(j,i)==1){
  57. fill(vis,vis+1005,false);
  58. con2[i][j] = true;
  59. }
  60. else{
  61. fill(vis,vis+1005,false);
  62. goto L;
  63. }
  64. }
  65. ans++;
  66. L:;
  67. }
  68. printf("%d",ans);
  69. }
  70. /*
  71. 4 4
  72. 1 2
  73. 1 3
  74. 2 4
  75. 3 4
  76. 2 1
  77. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement