社区讨论

为什么？？？？？

WWarren1022
学术版参与者 5已保存回复 21

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mm7ms60h
此快照首次捕获于
2026/03/01 18:52
6 天前
此快照最后确认于
2026/03/04 16:55
3 天前
查看原帖

求问为什么多开了变量会T？？？！！！

第一份代码：注释数组（结果）
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=2e6+5;
int f[N],sz[N],ed[N];
// int cnt[N],st;
int h[N],nx[M],to[M],tt;
void add(int u,int v){
    to[++tt]=v,nx[tt]=h[u],h[u]=tt;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void qry(int u,int v){
    u=find(u),v=find(v);
    if(u!=v){
        if(sz[u]>sz[v])swap(u,v);
        f[u]=v;
        sz[v]+=sz[u];
        ed[v]+=ed[u]+1;
    }
    else ed[u]++;
}
int c[N];
// void dfs(int u,int dep){
// 	int t=(dep==1)?2:1;
// 	cnt[u]=dep;
// 	for(int i=h[u];i;i=nx[i]){
// 		int j=to[i];
// 		if(cnt[j]){
// 			if(cnt[j]==t)continue;
// 			else{st=1;return;}
// 		}else{
// 			dfs(j,t);
// 			if(st)return;
// 		}
// 	}
// }
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _,id;
    cin>>id>>_;
    if(id==4){
        while(_--)puts("Yes");return 0;
    }
    // if(id==5){
    //     while(_--){
    //     int n,m,x,y;
    //     cin>>n>>m>>x>>y;
    //     for(int i=1;i<=n;i++)f[i]=i,sz[i]=1,ed[i]=0,h[i]=0,cnt[i]=0;
    //     tt=0;st=0;
    //     for(int i=1,u,v;i<=m;i++){
    //         cin>>u>>v;
    //         add(u,v);
    //         add(v,u);
    //         qry(u,v);
    //     }
    //     int rx=find(x),ry=find(y);
    //     if(rx!=ry){
    //         cout<<"No\n";
    //         continue;
    //     }
    //     int V=sz[rx],E=ed[rx];
    //     if(E<V){
    //         cout<<"No\n";
    //         continue;
    //     }dfs(x,0);
    //     if(st)cout<<"Yes\n";
    //     else if(cnt[y]==1)cout<<"Yes\n";
    //     else cout<<"No\n";
        
    // }
    //     return 0;
    // }
    while(_--){
        int n,m,x,y;
        cin>>n>>m>>x>>y;
        for(int i=1;i<=n;i++)f[i]=i,sz[i]=1,ed[i]=0,h[i]=0;
        tt=0;
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
            qry(u,v);
        }
        int rx=find(x),ry=find(y);
        if(rx!=ry){
            cout<<"No\n";
            continue;
        }
        int V=sz[rx],E=ed[rx];
        if(E<V){
            cout<<"No\n";
            continue;
        }
        queue<int>q;
        for(int i=1;i<=n;i++)c[i]=-1;
        c[x]=0;
        q.push(x);
        bool bp=1;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=h[u];i;i=nx[i]){
                int v=to[i];
                if(c[v]==-1){
                    c[v]=c[u]^1;
                    q.push(v);
                }else if(c[v]==c[u]){
                    bp=0;
                }
            }
        }
        if(!bp)cout<<"Yes\n";
        else{
            if(c[x]==c[y])cout<<"No\n";
            else cout<<"Yes\n";
        }
    }
    return 0;
}
第二份代码：不注释数组（结果）
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=2e6+5;
int f[N],sz[N],ed[N];
int cnt[N],st;
int h[N],nx[M],to[M],tt;
void add(int u,int v){
    to[++tt]=v,nx[tt]=h[u],h[u]=tt;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void qry(int u,int v){
    u=find(u),v=find(v);
    if(u!=v){
        if(sz[u]>sz[v])swap(u,v);
        f[u]=v;
        sz[v]+=sz[u];
        ed[v]+=ed[u]+1;
    }
    else ed[u]++;
}
int c[N];
// void dfs(int u,int dep){
// 	int t=(dep==1)?2:1;
// 	cnt[u]=dep;
// 	for(int i=h[u];i;i=nx[i]){
// 		int j=to[i];
// 		if(cnt[j]){
// 			if(cnt[j]==t)continue;
// 			else{st=1;return;}
// 		}else{
// 			dfs(j,t);
// 			if(st)return;
// 		}
// 	}
// }
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _,id;
    cin>>id>>_;
    if(id==4){
        while(_--)puts("Yes");return 0;
    }
    // if(id==5){
    //     while(_--){
    //     int n,m,x,y;
    //     cin>>n>>m>>x>>y;
    //     for(int i=1;i<=n;i++)f[i]=i,sz[i]=1,ed[i]=0,h[i]=0,cnt[i]=0;
    //     tt=0;st=0;
    //     for(int i=1,u,v;i<=m;i++){
    //         cin>>u>>v;
    //         add(u,v);
    //         add(v,u);
    //         qry(u,v);
    //     }
    //     int rx=find(x),ry=find(y);
    //     if(rx!=ry){
    //         cout<<"No\n";
    //         continue;
    //     }
    //     int V=sz[rx],E=ed[rx];
    //     if(E<V){
    //         cout<<"No\n";
    //         continue;
    //     }dfs(x,0);
    //     if(st)cout<<"Yes\n";
    //     else if(cnt[y]==1)cout<<"Yes\n";
    //     else cout<<"No\n";
        
    // }
    //     return 0;
    // }
    while(_--){
        int n,m,x,y;
        cin>>n>>m>>x>>y;
        for(int i=1;i<=n;i++)f[i]=i,sz[i]=1,ed[i]=0,h[i]=0;
        tt=0;
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
            qry(u,v);
        }
        int rx=find(x),ry=find(y);
        if(rx!=ry){
            cout<<"No\n";
            continue;
        }
        int V=sz[rx],E=ed[rx];
        if(E<V){
            cout<<"No\n";
            continue;
        }
        queue<int>q;
        for(int i=1;i<=n;i++)c[i]=-1;
        c[x]=0;
        q.push(x);
        bool bp=1;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=h[u];i;i=nx[i]){
                int v=to[i];
                if(c[v]==-1){
                    c[v]=c[u]^1;
                    q.push(v);
                }else if(c[v]==c[u]){
                    bp=0;
                }
            }
        }
        if(!bp)cout<<"Yes\n";
        else{
            if(c[x]==c[y])cout<<"No\n";
            else cout<<"Yes\n";
        }
    }
    return 0;
}

回复

共 21 条回复，欢迎继续交流。

正在加载回复...