QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53577#2341. Dead-End Detectornot_so_organicAC ✓225ms26452kbC++112.7kb2022-10-05 13:34:352022-10-05 13:34:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 13:34:37]
  • 评测
  • 测评结果:AC
  • 用时:225ms
  • 内存:26452kb
  • [2022-10-05 13:34:35]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}

const int N = 1000005;

int head[N], to[N * 2], nxt[N * 2], pre[N], deg[N], DEG[N], cnt = 1;

void add(int u, int v) {
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
    pre[cnt] = u;
}

int n, m;

void work1() {
    queue<int>Q;
    bool vis[N] = {0};

    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            Q.push(i), vis[i] = 1;

    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();

        for (int i = head[now]; i; i = nxt[i]) {
            int v = to[i];

            if (!vis[v] && (--deg[v]) == 1)
                Q.push(v), vis[v] = 1;
        }
    }
}

bool vis[N];

void work2() {
    queue<int>Q;

    for (int i = 1; i <= n; i++)
        if (deg[i] >= 2)
            Q.push(i), vis[i] = 1;

    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();

        for (int i = head[now]; i; i = nxt[i]) {
            int v = to[i];

            if (!vis[v] && deg[v] == 1)
                Q.push(v), vis[v] = 1;
        }
    }
}

vector<pair<int, int>>ans;

int main() {
    n = read(), m = read();

    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
        DEG[u]++, DEG[v]++;
        deg[u]++, deg[v]++;
    }

    work1();
    work2();

    //  for(int i=1;i<=n;i++)
    //      printf("%d %d %d\n",deg[i],DEG[i],vis[i]);
    for (int i = 1; i <= cnt; i += 2) {
        int x = pre[i], y = to[i];

        if (vis[x] || vis[y]) {
            //          printf("!!!%d %d\n",x,y);
            if ((deg[x] == 1 && deg[y] == 1) || (deg[x] > 1 && deg[y] > 1))
                continue;

            if (deg[x] == 1)
                ans.push_back(make_pair(y, x));
            else
                ans.push_back(make_pair(x, y));
        } else if (!vis[x] && !vis[y]) {
            if (DEG[y] == 1)
                ans.push_back(make_pair(y, x));

            if (DEG[x] == 1)
                ans.push_back(make_pair(x, y));
        }
    }

    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());

    for (int i = 0; i < (int)ans.size(); i++)
        printf("%d %d\n", ans[i].first, ans[i].second);

    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 3ms
memory: 4688kb

Test #2:

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

Test #3:

score: 0
Accepted
time: 86ms
memory: 24348kb

Test #4:

score: 0
Accepted
time: 3ms
memory: 4660kb

Test #5:

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

Test #6:

score: 0
Accepted
time: 1ms
memory: 4680kb

Test #7:

score: 0
Accepted
time: 3ms
memory: 4712kb

Test #8:

score: 0
Accepted
time: 4ms
memory: 4740kb

Test #9:

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

Test #10:

score: 0
Accepted
time: 3ms
memory: 4760kb

Test #11:

score: 0
Accepted
time: 3ms
memory: 4680kb

Test #12:

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

Test #13:

score: 0
Accepted
time: 26ms
memory: 16396kb

Test #14:

score: 0
Accepted
time: 61ms
memory: 16452kb

Test #15:

score: 0
Accepted
time: 175ms
memory: 24864kb

Test #16:

score: 0
Accepted
time: 190ms
memory: 25868kb

Test #17:

score: 0
Accepted
time: 202ms
memory: 26448kb

Test #18:

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

Test #19:

score: 0
Accepted
time: 3ms
memory: 4680kb

Test #20:

score: 0
Accepted
time: 3ms
memory: 4804kb

Test #21:

score: 0
Accepted
time: 3ms
memory: 4764kb

Test #22:

score: 0
Accepted
time: 36ms
memory: 12276kb

Test #23:

score: 0
Accepted
time: 66ms
memory: 24440kb

Test #24:

score: 0
Accepted
time: 40ms
memory: 22332kb

Test #25:

score: 0
Accepted
time: 95ms
memory: 22128kb

Test #26:

score: 0
Accepted
time: 43ms
memory: 24440kb

Test #27:

score: 0
Accepted
time: 90ms
memory: 24388kb

Test #28:

score: 0
Accepted
time: 63ms
memory: 24344kb

Test #29:

score: 0
Accepted
time: 64ms
memory: 24340kb

Test #30:

score: 0
Accepted
time: 82ms
memory: 20240kb

Test #31:

score: 0
Accepted
time: 164ms
memory: 20156kb

Test #32:

score: 0
Accepted
time: 114ms
memory: 25888kb

Test #33:

score: 0
Accepted
time: 225ms
memory: 25896kb

Test #34:

score: 0
Accepted
time: 146ms
memory: 22616kb

Test #35:

score: 0
Accepted
time: 177ms
memory: 24328kb

Test #36:

score: 0
Accepted
time: 161ms
memory: 24376kb

Test #37:

score: 0
Accepted
time: 152ms
memory: 24260kb

Test #38:

score: 0
Accepted
time: 194ms
memory: 24824kb

Test #39:

score: 0
Accepted
time: 150ms
memory: 22932kb

Test #40:

score: 0
Accepted
time: 134ms
memory: 23832kb

Test #41:

score: 0
Accepted
time: 150ms
memory: 23124kb

Test #42:

score: 0
Accepted
time: 146ms
memory: 23532kb

Test #43:

score: 0
Accepted
time: 136ms
memory: 23592kb

Test #44:

score: 0
Accepted
time: 205ms
memory: 26452kb

Test #45:

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