QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#677299#995. 桥oyzrWA 76ms17408kbC++201.6kb2024-10-26 11:02:272024-10-26 11:02:28

Judging History

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

  • [2024-10-26 11:02:28]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:17408kb
  • [2024-10-26 11:02:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5, MAXM = 5e5 + 5;
int read(){
    int res = 0, flag = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            flag = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        res = (res << 1) + (res << 3) + (c ^ 48);
    return res * flag;
}
class Graph{
private:
    const static int MAXNODE = MAXN;
    const static int MAXEDGE = 2 * MAXM;
    struct Edge{
        int v, next;
    };
public:
    int tot = 1;
    int h[MAXNODE];
    Edge t[MAXEDGE]; 
    void addEdge(int u, int v){
        ++tot;
        t[tot].v = v;
        t[tot].next = h[u];
        h[u] = tot;
    }
}G;
int cnt = 0;
int dfn[MAXN], low[MAXN];
int cut[2 * MAXM];
void dfs(int u, int from){
    dfn[u] = low[u] = ++cnt;
    for (int i = G.h[u]; i; i = G.t[i].next){
        if ((i ^ 1) == from)
            continue;   
        int v = G.t[i].v;
        if (!dfn[v]){
            dfs(v, i);
            low[u] = min(low[u], low[v]);
        }else{
            low[u] = min(low[u], dfn[v]);
        }
        if (low[v] > low[u])
            cut[i] = 1;
    }
}
int main(){
    int n = read(), m = read();
    for (int i = 1; i <= m; i++){
        int u = read(), v = read();
        G.addEdge(u, v);
        G.addEdge(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            dfs(i, 0);
    for (int i = 2; i <= G.tot; i += 2){
        if (cut[i])
            cout << G.t[i ^ 1].v << ' ' << G.t[i].v << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 76ms
memory: 17408kb

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:

12556 21443
11073 24296
5073 12731
22550 14761
15118 13639
9278 4127
7457 21674
17693 23448
10949 23429
7742 15164
17336 1662
6540 11942
11 4937
22639 15901
6021 9982
12453 48
8540 4247
10074 20877
16990 18030
11159 22933
23086 9796
11806 8256
4135 22929
16138 4024
4859 13423
10484 14755
14162 22810...

result:

wrong output format Extra information in the output file