CS Academy #62 (Div.2) C
もう解説通りにやるだけで大変だったんですけど、どうしようもないエラーも出ず、計算も意外と速かったです。
#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; struct edge{int from, to;}; vector<bool> bfs(int u, vector<int> v[]){ vector<bool> visited(1000); fill(visited.begin(), visited.end(), false); visited[u] = true; queue<int> qa; qa.push(u); while(!qa.empty()){ int s = qa.front(); qa.pop(); for(int i = 0; i < v[s].size(); i++){ if(visited[v[s][i]] == false){ visited[v[s][i]] = true; qa.push(v[s][i]); } } } return visited; } bool is_bridge(int N, vector<int> adj[]){ vector<bool> visited = bfs(0, adj); if(visited.size() < N) return true; for(int i = 0; i < N; i++){ if(!visited[i]) return true; } return false; } int main(){ int N, M, Q; vector<edge> es, es1; vector<bool> bridge; cin >> N >> M >> Q; vector<int> adj[1000]; for(int i = 0; i < M; i++){ int x, y; cin >> x >> y; x--; y--; es1.push_back((edge){x, y}); } for(int i = 0; i < M; i++){ es.clear(); for(int j = 0; j < M; j++){ if(i == j) continue; es.push_back(es1[j]); } for(int j = 0; j < N; j++) adj[j].clear(); for(int j = 0; j < es.size(); j++){ adj[es[j].from].push_back(es[j].to); adj[es[j].to].push_back(es[j].from); } if(is_bridge(N, adj)) bridge.push_back(true); else bridge.push_back(false); } vector<int> adj2[1000]; for(int i = 0; i < M; i++){ if(bridge[i]){ adj2[es1[i].from].push_back(es1[i].to); adj2[es1[i].to].push_back(es1[i].from); } } for(int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; vector<bool> visited = bfs(x, adj2); if(visited[y]) cout << 1 << endl; else cout << 0 << endl; } return 0; }
余談ですけど、この回の配点100-200-500-400-800って罠ですかね