4 solutions

  • 2
    @ 2022-4-6 16:06:14
    #include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    static const int MAX = 10007;
    static const int NIL = -1;
    
    //使用vector实现邻接表
    int n;
    vector<int>G[MAX];
    int color[MAX];
    
    //深搜实现连通图的染色
    void dfs(int r,int c){
    	stack<int>S;
    	S.push(r);
    	color[r]=c;
    	while(!S.empty()){
    		int u=S.top();S.pop();
    		for(int i=0;i<G[u].size();i++){
    			int v=G[u][i];
    			if(color[v]==NIL){
    				color[v]=c;
    				S.push(v);
    			}
    		}
    	}
    }
    
    //遍历图,逐个染色
    void assignColor(){
    	int id=1;
    	for(int i=0;i<=n;i++)color[i]=NIL;
    	for(int i=0;i<=n;i++){
    		if(color[i]==NIL)dfs(i,id++);
    	}
    }
    
    int main(){
    	int s,t,m,q;
    	
    	cin>>n>>m>>q;
    	
    	for(int i=0;i<m;i++){
    		cin>>s>>t;
    		G[s].push_back(t);
    		G[t].push_back(s);
    	}
    	
    	assignColor();
    	
    	for(int i=0;i<q;i++){
    		cin>>s>>t;
    		if(color[s]==color[t])cout<<"Yes"<<endl;
    		else cout<<"No"<<endl;
    	}
    	
    	return 0;
    }
    

    Information

    ID
    1257
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    4
    Tags
    # Submissions
    141
    Accepted
    66
    Uploaded By