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で計算する.
参照コード:
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<