Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n,m;
- bool con1[1005][1005] = {false};
- bool con2[21005][1005] = {false};
- bool vis[1005] = {false};
- vector<int> dep[1005];
- int iscon1(int x,int y){
- if(con1[x][y]==true) return 1;
- for(int i = 0;i < dep[x].size();i++){
- if(vis[dep[x][i]]==false){
- vis[dep[x][i]] = true;
- if(iscon1(dep[x][i],y)==1)
- return 1;
- }
- }
- return 0;
- }
- int iscon2(int x,int y){
- if(con2[y][x]==true) return 1;
- for(int i = 0;i < dep[x].size();i++){
- if(vis[dep[x][i]]==false){
- vis[dep[x][i]] = true;
- if(iscon2(dep[x][i],y)==1)
- return 1;
- }
- }
- return 0;
- }
- int main(){
- int a,b,ans = 0;
- scanf("%d%d",&n,&m);
- for(int i = 0;i < m;i++){
- scanf("%d%d",&a,&b);
- dep[a].push_back(b);
- }
- for(int i = 1;i <= n;i++){
- con1[i][i] = con2[i][i] = true;
- }
- for(int i = 1;i <= n;i++){
- for(int j = 1;j <= n;j++){
- if(iscon1(i,j)==1){
- fill(vis,vis+1005,false);
- con1[i][j] = true;
- }
- else if(iscon2(j,i)==1){
- fill(vis,vis+1005,false);
- con2[i][j] = true;
- }
- else{
- fill(vis,vis+1005,false);
- goto L;
- }
- }
- ans++;
- L:;
- }
- printf("%d",ans);
- }
- /*
- 4 4
- 1 2
- 1 3
- 2 4
- 3 4
- 2 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement