Demo entry 6646139

韩书楷

   

Submitted by anonymous on Oct 15, 2017 at 14:09
Language: C++. Code size: 1.6 kB.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
vector<int>grap[maxn];
struct Edge {
    int u, v;
    Edge(int u, int v) {
        this->u = u;
        this->v = v;
    }
};
stack<Edge> e_stack;
int DFN[maxn], L[maxn];
int cnt;
void init() {
    cnt = 1;
    memset(DFN, 0, sizeof(DFN));
    while(!e_stack.empty())
        e_stack.pop();
}
void input() {
    freopen("2-5.txt", "r", stdin);
    int n, u, v;
    scanf("%d", &n);
    for(int i = 0; i <= n; i++)
        grap[i].clear();
    while(scanf("%d %d", &u, &v) != EOF) {
        grap[u].push_back(v);
        grap[v].push_back(u);
    }
}
int DFNL(int u, int v) {
    DFN[u] = L[u] = cnt++;
    int size = grap[u].size();
    for(int i = 0; i < size; i++) {
        int w = grap[u][i];
        if(w != v && DFN[w] < DFN[u]) {
            e_stack.push(Edge(u, w));
        }
        if(DFN[w] == 0) {
            L[u] = min(L[u], DFNL(w, u));
            if(L[w] >= DFN[u]) {
                printf("-----\n");
                do {
                    Edge edge = e_stack.top();
                    e_stack.pop();
                    printf("(%d, %d)\n", edge.u, edge.v);
                    if((edge.u == w && edge.v == u) || \
                        (edge.u == u && edge.v == w))
                        break;
                } while(true);
            }
        }
        else {
            L[u] = min(L[u], DFN[w]);
        }
    }
    return L[u];
}
int main() {
    init();
    input();
    DFNL(1, 0);
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).