关于复杂度……

回复帖子

@洛谷亿岁 2019-06-11 18:08 回复
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstdio>

using namespace std;
bool vis[1005][1005];
int x[105],y[105];
int ans;
int n;
void dfs(int x1,int y1){
//    puts("1");
    vis[x1][y1]=false;
    for(int i=0;i<1001;i++){
        if(vis[i][y1]){
            dfs(i,y1);
        }
    }
    for(int i=0;i<1005;i++){
        if(vis[x1][i]){
            dfs(x1,i);
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
        vis[x[i]][y[i]]=true;
    }
    for(int i=0;i<n;i++){
        if(vis[x[i]][y[i]]){
            dfs(x[i],y[i]);
            ans++;
        }
    }
    cout<<ans-1<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstdio>

using namespace std;
bool vis[1005][1005];
int ans;
int n;
void dfs(int x1,int y1){
    vis[x1][y1]=false;
    for(int i=0;i<1001;i++){
        if(vis[i][y1]){
            dfs(i,y1);
        }
    }
    for(int i=0;i<1005;i++){
        if(vis[x1][i]){
            dfs(x1,i);
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        vis[x][y]=true;
    }
    for(int i=0;i<1001;i++){
        for(int j=0;j<1001;j++){
            if(vis[i][j]){
                ans++;
                dfs(i,j);
            }
        }
    }
    cout<<ans-1<<endl;
    return 0;
}

哪个时间复杂度高啊???(不用管我这个蒟蒻,回答就可以了,谢谢

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。