QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#265901 | #2341. Dead-End Detector | InfinityNS# | AC ✓ | 399ms | 93752kb | C++14 | 3.7kb | 2023-11-25 22:13:28 | 2023-11-25 22:13:29 |
Judging History
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