Google Kickstart Round C 2018 Problem A. Planet Distance
4186 ワード
ProblemA.Planet Distanceテーマ転送ゲート:https://code.google.com/codejam/contest/4384486/dashboard#s=p0
私のやり方はまずKahnアルゴリズムでリング内のすべてのノードを見つけることです.次に、全ての点からリングまでの最近接距離を一度のBFSで計算する.
参照コード:
私のやり方はまずKahnアルゴリズムでリング内のすべてのノードを見つけることです.次に、全ての点からリングまでの最近接距離を一度のBFSで計算する.
参照コード:
int main()
{
int no;
cin>>no;
for (int nn=1;nn<=no;nn++){
int n,a,b;
cin>>n;
vector<vector<int>> edge(n);
vector<int> degree(n);
vector<bool> live(n,true);
vector<int> dist(n);
for (int i=0;icin>>a>>b;
edge[a-1].push_back(b-1);
degree[b-1]++;
edge[b-1].push_back(a-1);
degree[a-1]++;
}
//find the circle
queue<int> q;
for (int i=0;iif (degree[i]==1)
q.push(i);
while (!q.empty()){
int cur=q.front();
q.pop();
live[cur]=false;
degree[cur]--;
for (int i=0;iif (live[edge[cur][i]] && (--degree[edge[cur][i]]==1)){
q.push(edge[cur][i]);
}
}
//calculate distances using BFS
for (int i=0;iif (degree[i]!=0){
q.push(i);
dist[i]=0;
}
while (!q.empty()){
int cur=q.front();
q.pop();
for (int i=0;iif (!live[edge[cur][i]]){
dist[edge[cur][i]]=dist[cur]+1;
live[edge[cur][i]]=true;
q.push(edge[cur][i]);
}
}
cout<<"Case #"<":";
for (int i=0;icout<<" "<cout<