SHARE
TWEET

Untitled

a guest Dec 14th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top