QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473152 | #995. 桥 | Williamxzh# | RE | 0ms | 0kb | C++23 | 1.1kb | 2024-07-11 22:32:41 | 2024-07-11 22:32:42 |
answer
#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,m,dfn[N],low[N],cnt,vis[N];pii g[N*5];
int st[N],top,bel[N],idx;
vector<pii> e[N];
il void adde(int x,int y,int z){e[x].push_back({y,z});}
void tarjan(int x,int pre){
int y,z;dfn[x]=low[x]=++cnt,st[++top]=x;
for(auto it:e[x]){
y=it.fi,z=it.se;if(z==pre) continue;
if(!dfn[y]) tarjan(y,z),low[x]=min(low[x],low[y]);
else low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
++idx;
do{
y=st[top--],bel[y]=idx;
}while(y!=x);
}
}
int x,y;
int main(){
//freopen("bridge.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);if(x!=y) adde(x,y,i),adde(y,x,i);
g[i]={x,y};
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0),top=0;
for(int i=1;i<=n;++i)
for(auto it:e[i]) if(bel[i]!=bel[it.fi]) vis[it.se]=1;
for(int i=1;i<=m;++i) if(vis[i]) printf("%d %d\n",g[i].fi,g[i].se);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
24942 387166 12556 21443 22404 16376 11073 24296 1535 11968 23745 2818 5073 12731 22550 14761 24118 12008 22695 18979 15118 13639 2080 8721 692 22578 22581 15267 9278 4127 7457 21674 17693 23448 10949 23429 9700 6009 14140 5064 7742 15164 17336 1662 18903 9760 17645 19575 6540 11942 11 4937 15282 10...
output:
13175 22566 3443 6209 15136 5705 5774 8826 17960 9282 19771 6092 24196 349 15098 17190 21282 4468 20160 20204 2662 11211 8319 11717 88 22264 1373 8238 14235 14025 4522 6345 12585 21983 17377 20832 8899 13520 3605 6415 11609 4410 16288 19670 18587 19305 8382 1205 324 20518 8918 254 17902 22689 9735 7...