1 条题解

  • 0
    @ 2023-2-3 15:28:42
    1563题的题解
    #include<bits/stdc++.h>
    using namespace std;
    
    int read(){
    	int ans = 0, f = 1;
    	char ch = getchar();
    	while(!isdigit(ch)){
    		f = (ch=='-') ? -1 : 1;
    		ch = getchar();
    	}
    	while(isdigit(ch)){
    		ans = (ans<<1)+(ans<<3)+(ch^48);
    		ch = getchar();
    	}
    	return ans*f;
    }
    
    const int MAXX = 5e3;
    int n, m, sum;
    int g[MAXX][MAXX], flag[MAXX];
    
    void dfs(int x){
    	if(sum>n) return;
    	sum++;
    	flag[x] = 1;
    	if(x == 1) printf("1");
    	else printf("-%d",x);
    	int t = 0;
    	for(int i=1; i<=n; i++){
    		if(g[x][i]==1 && (!flag[i])){
    			dfs(i);
    		}
    	}
    }
    
    queue <int> q;
    
    void bfs(){
    	flag[1] = 1;
    	q.push(1);
    	sum++;
    	while(sum<n){
    		if(q.empty()){
    			for(int i=1; i<=n; i++){
    				if(!flag[i]){
    					q.push(i);
    					flag[i] = 1;
    					sum++;
    				}
    			}
    		}
    		int x = q.front();
    		for(int i=1; i<=n; i++){
    		if(g[x][i]==1 && (!flag[i])){
    			q.push(i);
    			flag[i] = 1;
    			sum++;
    			}
    		}
    		if(x == 1) printf("1");
    		else{
    			printf("-%d", q.front());
    		}
    		q.pop();
    	}
    	while(!q.empty()){
    		printf("-%d",q.front());
    		q.pop();
    	}
    	return;
    }
    
    int main(){
    	n = read(), m = read();
    	memset(g, 0x3f, sizeof(g));
    	for(int i=1; i<=m; i++){
    		int a =  read(), b = read();
    		g[a][b] = 1 ;
    		g[b][a] = 1 ;
    	}
    	for(int i=1; i<=n; i++){
    		g[i][i] = 0;
    	}
    	dfs(1);
    	while(sum<n){
    		for(int i=1; i<=n; i++){
    			if(!flag[i]) dfs(i);
    		}
    	}
    	cout<<endl;
    	memset(flag, 0, sizeof(flag));
    	sum = 0;
    	bfs();
    	return 0;
    }
    

    信息

    ID
    815
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    7
    已通过
    1
    上传者