会津大学オンラインジャッジ ＧＲＬ＿３＿Ａ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A

Ｃonnected Components - Articulation Points
完全に自己流の解放で解決。

問題ページのヒントへのリンクに解法が載っているがそれはガン無視。
まずは全くの0から自分で考えた解法で解いてみた。
中学生レベルの教育も満足に受けてないしグラフ理論なんてわかんねというのでとにかく時間かかった。

コードの方針を決めるのに２時間。
一睡しながら夢の中で考え直し、そのあとは試行錯誤しながらコード実装をガリガリ６時間。
実質３日かかった。

コード実行時間0.03セコンド、正答者の中では実行速度最下位である。
残念。

そのうちヒントのほうの解法を実装しようと思う。


#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<set>
#include<stack>


struct E{
    int t,len,old,no;
    bool alive;
    bool operator<(const E& e1)const{
        return len>e1.len;
    }
};

const int LIMIT=10*10000+1;
std::vector<E> G[LIMIT];
int lens[LIMIT];
int roots[LIMIT];

bool alivePoints[LIMIT];
int  loopCounts[LIMIT];
int size;


void D(){
    E e1,e2;
    int v,e,s,t;
    scanf("%d %d",&v,&e);
   
    for(int i=0;i<e;i++){
        scanf("%d %d",&s,&t);
        e1.alive=false;
        e1.len=0;
        e1.t=t;
        G[s].push_back(e1);
        e1.t=s;
        G[t].push_back(e1);
    }
    memset(lens,-1,sizeof(lens));
    e1.old=-1;
    e1.t=0;
    e1.len=0;
    e1.no=0;
    std::priority_queue<E> pq;
    pq.push(e1);
    std::vector<E>::iterator vIt,vItEnd;
    size=v;
    while(pq.empty()==false){
        e1=pq.top();
        pq.pop();
        if(lens[e1.t]!=-1&&lens[e1.t]<=e1.len){
            continue;
        }
        lens[e1.t]=e1.len;
       
        if(e1.old!=-1){
            //printf("(a t=%d old=%d no=%d)\n",e1.t,e1.old,e1.no);
            G[e1.old][e1.no].alive=true;
            roots[e1.t]=e1.old;
        }
       
        e1.len++;
        vItEnd=G[e1.t].end();
        int i=0;
        for(vIt=G[e1.t].begin();vIt!=vItEnd;vIt++){
            e2=(*vIt);
            e2.len=e1.len;
            e2.old=e1.t;
            e2.no=i;
            i++;
            if(e2.t==e1.old){
                //printf("(b old=%d t=%d no=%d)\n",e2.old, e2.t, e2.no);
                G[e2.old][e2.no].alive=true;
            }else{
                pq.push(e2);
            }
        }
    }
    //std::set<int>::iterator sIt;
    //for(int i=0;i<v;i++){
    //  printf("\n%d\n",i);
    //  for(sIt=pareMemo[i].begin();sIt!=pareMemo[i].end();sIt++){
    //      printf("<%d> ",(*sIt));
    //  }
    //}
}


std::map<int,int> memo;
int countNos[LIMIT];
int nowLoopAdds[LIMIT];
int dells[LIMIT];
bool ans[LIMIT];

bool lastPoint0Check(){
    //この関数はとても恥ずかしい
    if(size<3)return false;
    if(G[0].size()==1)return false;
    std::queue<int> qu;
    qu.push(1);
    memset(alivePoints,true,sizeof(alivePoints));
    alivePoints[0]=alivePoints[1]=false;
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    while(qu.empty()==false){
        int p=qu.front();
        qu.pop();
        vItEnd=G[p].end();
        for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
            int p1=(*vIt).t;
            if(alivePoints[p1]==false)continue;
            alivePoints[p1]=false;
            qu.push(p1);
        }
    }
    for(int i=0;i<size;i++){
        if(alivePoints[i]==true)return true;
    }
    return false;
}

void search(){
    memset(alivePoints,true,sizeof(alivePoints));
    memset(loopCounts,0,sizeof(loopCounts));
    memset(ans,false,sizeof(ans));
    memset(nowLoopAdds,0,sizeof(nowLoopAdds));
    memset(dells,0,sizeof(dells));

    std::stack<std::pair<int,int> > sta;
    std::pair<int,int> pp,pp2;
    alivePoints[0]=false;
    pp.first=0;
    pp.second=0;
    sta.push(pp);
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    int countNo=0;
    while(sta.empty()==false){
        countNo++;
        pp=sta.top();
        sta.pop();
       
        int s=pp.first;
        int i=pp.second;
        //printf("%d ",s);
        alivePoints[s]=false;
        if(i==G[s].size()){
            int t=countNos[s];
            memo.erase(t);
            if(s!=0){
                loopCounts[roots[s]]+=loopCounts[s]+nowLoopAdds[s]-dells[s];
                if((loopCounts[s]==dells[s])&&((nowLoopAdds[s]+loopCounts[s]==0)||(dells[s]>0))){
                    ans[s]=true;
                    if(nowLoopAdds[s]==0){
                        ans[roots[s]]=true;
                    }
                }
            }
           
            //printf("\n<d=%d>\n",t);
            //std::map<int,int>::iterator sIt;
            //for(sIt=memo.begin();sIt!=memo.end();sIt++){
            //  printf("<%d %d>",(*sIt).first,(*sIt).second);
            //}
            //printf("\n");
        }else{
            if(i==0){
                memo[countNo]=s;
            }else{
                int t=countNos[s];
                memo.erase(t);
                memo[countNo]=s;
            }
            countNos[s]=countNo;
            //printf("(%d %d)",s,countNo);
           
            e1=G[s][pp.second];
            pp.second++;
            sta.push(pp);
            if(e1.alive==false&&alivePoints[e1.t]==true){
                nowLoopAdds[s]++;
            }
           
            if(alivePoints[e1.t]==false&&e1.alive==false){
                int dellP=(*(memo.upper_bound(countNos[e1.t]))).second;
                nowLoopAdds[s]++;
                //printf("\n<dell=%d t=%d s=%d>\n",dellP,e1.t,s);
                dells[dellP]+=2;
                continue;
            }
            if(alivePoints[e1.t]==false){
                continue;
            }
            if(e1.alive==true){
                pp2.first=e1.t;
                pp2.second=0;
                sta.push(pp2);
            }
        }
    }
   
    ans[0]=lastPoint0Check();
    for(int i=0;i<size;i++){
        if(ans[i]==true&&G[i].size()>1){
            printf("%d\n",i);
        }
        //printf("(i=%d count=%d dell=%d %d)\n",i,loopCounts[i],dells[i],roots[i]);
    }
}

int main(){
    D();
    search();
}