QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265901#2341. Dead-End DetectorInfinityNS#AC ✓399ms93752kbC++143.7kb2023-11-25 22:13:282023-11-25 22:13:29

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 22:13:29]
  • 评测
  • 测评结果:AC
  • 用时:399ms
  • 内存:93752kb
  • [2023-11-25 22:13:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
typedef pair<int,int>pii;

const int maxn=5e5+10;

vector<pii>vect[maxn];
int n,m,dsctime,disc[maxn],mind[maxn],isbridge[maxn],pos[maxn],bniz[maxn];

void go(int x,int prv){

    dsctime++;
    disc[x]=dsctime;
    mind[x]=dsctime;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i].ff;
        int eid=vect[x][i].ss;
        if(id==prv)continue;
        if(disc[id]==0){
            go(id,x);
            mind[x]=min(mind[x],mind[id]);
        }
        else{
            if(disc[id]<disc[x])mind[x]=min(mind[x],disc[id]);
        }


        if(mind[id]>disc[x])isbridge[eid]=1;
    }
}
void go2(int x,vector<int>&cand){

    pos[x]=1;
    cand.pb(x);
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i].ff;
        int eid=vect[x][i].ss;
        if(pos[id])continue;
        if(isbridge[eid])continue;
        go2(id,cand);
    }

}
void prek_bicbool(){

    for(int i=1;i<=n;i++){
        if(disc[i])continue;
        go(i,0);
    }

    for(int i=1;i<=n;i++){
        if(pos[i])continue;
        vector<int>cand;
        go2(i,cand);
        if(cand.size()>1){
            for(auto x:cand)bniz[x]=1;
        }
    }

    //for(int i=1;i<=n;i++){
       // printf("%d %d\n",i,bniz[i]);
    //}

}

bool vis[maxn];
vector<int> comp;
vector<int> deg(maxn);
vector<bool> inside(maxn);
void dfs(int tr){
    comp.pb(tr);
    vis[tr]=1;
    for(auto p:vect[tr]){
        if(!vis[p.f]){
            dfs(p.f);
        }
    }
}
int main(){

    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        vect[u].pb({v,i});
        vect[v].pb({u,i});
    }
    prek_bicbool();
    /*for(int i=1;i<=n;i++){
        printf("%i: %i\n",i,bniz[i]);
    }*/
    vector<pair<int,int>> ans;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            comp.clear();
            dfs(i);
            bool has=0;
            for(auto p:comp){
                if(bniz[p]){
                    has=1;
                }
                for(auto d:vect[p]){
                    deg[d.f]++;
                }
            }
            if(!has){
                for(auto p:comp){
                    if(deg[p]==1){
                        ans.pb({p,vect[p][0].f});
                    }
                }
            }
            else{

                queue<int> q;
                for(auto p:comp){
                    inside[p]=1;
                    if(deg[p]==1){
                        q.push(p);
                    }
                }
                while(q.size()){
                    int tr=q.front();
                    inside[tr]=0;
                    q.pop();
                    for(auto p:vect[tr]){
                        if(inside[p.f]){
                            deg[p.f]--;
                            if(deg[p.f]==1&&!bniz[p.f]){
                                q.push(p.f);
                            }
                        }
                    }
                }
                for(auto p:comp){
                    if(!inside[p]){
                        for(auto d:vect[p]){
                            if(inside[d.f]){
                                ans.pb({d.f,p});
                            }
                        }
                    }
                }
            }

        }
    }
    sort(ans.begin(),ans.end());
    printf("%i\n",ans.size());
    for(auto p:ans){
        printf("%i %i\n",p.f,p.s);
    }

    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 0ms
memory: 21108kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 21384kb

Test #3:

score: 0
Accepted
time: 207ms
memory: 92264kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 20260kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 20944kb

Test #6:

score: 0
Accepted
time: 0ms
memory: 21320kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 21588kb

Test #8:

score: 0
Accepted
time: 18ms
memory: 24524kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 22140kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 21688kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 23240kb

Test #12:

score: 0
Accepted
time: 5ms
memory: 21004kb

Test #13:

score: 0
Accepted
time: 56ms
memory: 28684kb

Test #14:

score: 0
Accepted
time: 59ms
memory: 28468kb

Test #15:

score: 0
Accepted
time: 259ms
memory: 51672kb

Test #16:

score: 0
Accepted
time: 224ms
memory: 51912kb

Test #17:

score: 0
Accepted
time: 231ms
memory: 55800kb

Test #18:

score: 0
Accepted
time: 242ms
memory: 55716kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 21988kb

Test #20:

score: 0
Accepted
time: 2ms
memory: 21992kb

Test #21:

score: 0
Accepted
time: 2ms
memory: 22612kb

Test #22:

score: 0
Accepted
time: 92ms
memory: 31480kb

Test #23:

score: 0
Accepted
time: 287ms
memory: 71432kb

Test #24:

score: 0
Accepted
time: 107ms
memory: 89848kb

Test #25:

score: 0
Accepted
time: 289ms
memory: 87616kb

Test #26:

score: 0
Accepted
time: 96ms
memory: 93712kb

Test #27:

score: 0
Accepted
time: 316ms
memory: 92576kb

Test #28:

score: 0
Accepted
time: 399ms
memory: 93752kb

Test #29:

score: 0
Accepted
time: 341ms
memory: 93640kb

Test #30:

score: 0
Accepted
time: 96ms
memory: 46556kb

Test #31:

score: 0
Accepted
time: 184ms
memory: 46424kb

Test #32:

score: 0
Accepted
time: 130ms
memory: 54916kb

Test #33:

score: 0
Accepted
time: 231ms
memory: 54828kb

Test #34:

score: 0
Accepted
time: 340ms
memory: 82684kb

Test #35:

score: 0
Accepted
time: 260ms
memory: 48860kb

Test #36:

score: 0
Accepted
time: 268ms
memory: 55988kb

Test #37:

score: 0
Accepted
time: 290ms
memory: 65064kb

Test #38:

score: 0
Accepted
time: 264ms
memory: 45936kb

Test #39:

score: 0
Accepted
time: 228ms
memory: 44508kb

Test #40:

score: 0
Accepted
time: 296ms
memory: 60824kb

Test #41:

score: 0
Accepted
time: 273ms
memory: 48832kb

Test #42:

score: 0
Accepted
time: 267ms
memory: 45456kb

Test #43:

score: 0
Accepted
time: 279ms
memory: 46824kb

Test #44:

score: 0
Accepted
time: 241ms
memory: 55860kb

Test #45:

score: 0
Accepted
time: 227ms
memory: 55812kb