4 solutions
-
2
#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