2018-Sp11-lyk/G

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
typedef pair<int, int> pii;
pii mark[maxn];
vector<pii> pG;
int depth[maxn], parent[maxn];
vector<int> ans[3];
vector<int> G[maxn];

void DFS(int u){
    //printf("%d %d\n", u, parent[u]);
    for(int v: G[u])
        if(depth[v] == 0){
            depth[v] = depth[parent[v] = u] + 1;
            DFS(v); 
        }
        else if(parent[u] != v && depth[u] > depth[v]){
            pG.push_back(pii(u, v));
        }
}

int main(){
    freopen("grand.in", "r", stdin);
    freopen("grand.out", "w", stdout);
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t += 1){
        int n, m;
        scanf("%d %d", &n, &m);
        fill(depth, depth + n + 1, 0);
        fill(mark, mark + n + 1, pii(0, 0));
        for_each(G, G + n + 1, [](vector<int> &v){v.clear();});
        for(int i = 0; i < m; i += 1){
            int u, v;
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int S = 0, F = 0;
        pii x, y;
        for(int i = 1; i <= n; i += 1) if(depth[i] == 0){
            pG.clear();
            depth[i] = 1;
            parent[i] = 0;
            DFS(i);
            for(pii p: pG){
                for(int u = p.first; u != p.second; u = parent[u])
                    if(mark[u] == pii(0, 0)) mark[u] = p;
                    else{
                        x = mark[u];
                        y = p;
                        if(depth[x.second] > depth[y.second]) S = x.second;
                        else S = y.second;
                        F = u;
                        break;
                    }
                if(S) break;
            }
            if(S){
                for_each(ans, ans + 3, [](vector<int> &v){v.clear();});
                for(int u = S; u != x.second; u = parent[u]) ans[0].push_back(parent[u]);
                for(int u = x.first; u != F; u = parent[u]) ans[0].push_back(u);
                for(int u = S; u != y.second; u = parent[u]) ans[1].push_back(parent[u]);
                for(int u = y.first; u != F; u = parent[u]) ans[1].push_back(u);
                for(int u = parent[F]; u != S; u = parent[u]) ans[2].push_back(u);
                reverse(ans[2].begin(), ans[2].end()); 
                printf("%d %d\n", S, F);
                for_each(ans, ans + 3, [&](vector<int> &v){
                    printf("%d %d ", (int)v.size() + 2, S);
                    for(int x: v) printf("%d ", x);
                    printf("%d\n", F);
                });
                break;
            }
        }
        if(S == 0) printf("-1\n");
    }
}
}}}

#include<bits/stdc++.h>
#define maxn 120000
using namespace std;
typedef pair<int, int> pii;
pii mark[maxn];
vector<pii> pG;
int depth[maxn], parent[maxn];
vector<int> ans[3];
vector<int> G[maxn];
void DFS(int u){
    //printf("%d %d\n", u, parent[u]);
    for(int v: G[u])
        if(depth[v] == 0){
            depth[v] = depth[parent[v] = u] + 1;
            DFS(v); 
        }
        else if(parent[u] != v && depth[u] > depth[v]){
            pG.push_back(pii(u, v));
        }
}
int main(){
    freopen("grand.in", "r", stdin);
    freopen("grand.out", "w", stdout);
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t += 1){
        int n, m;
        scanf("%d %d", &n, &m);
        fill(depth, depth + n + 1, 0);
        fill(mark, mark + n + 1, pii(0, 0));
        for_each(G, G + n + 1, [](vector<int> &v){v.clear();});
        for(int i = 0; i < m; i += 1){
            int u, v;
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int S = 0, F = 0;
        pii x, y;
        for(int i = 1; i <= n; i += 1) if(depth[i] == 0){
            pG.clear();
            depth[i] = 1;
            parent[i] = 0;
            DFS(i);
            for(pii p: pG){
                for(int u = p.first; u != p.second; u = parent[u])
                    if(mark[u] == pii(0, 0)) mark[u] = p;
                    else{
                        x = mark[u];
                        y = p;
                        if(depth[x.second] > depth[y.second]) S = x.second;
                        else S = y.second;
                        F = u;
                        break;
                    }
                if(S) break;
            }
            if(S){
                for_each(ans, ans + 3, [](vector<int> &v){v.clear();});
                for(int u = S; u != x.second; u = parent[u]) ans[0].push_back(parent[u]);
                for(int u = x.first; u != F; u = parent[u]) ans[0].push_back(u);
                for(int u = S; u != y.second; u = parent[u]) ans[1].push_back(parent[u]);
                for(int u = y.first; u != F; u = parent[u]) ans[1].push_back(u);
                for(int u = parent[F]; u != S; u = parent[u]) ans[2].push_back(u);
                reverse(ans[2].begin(), ans[2].end()); 
                printf("%d %d\n", S, F);
                for_each(ans, ans + 3, [&](vector<int> &v){
                    printf("%d %d ", (int)v.size() + 2, S);
                    for(int x: v) printf("%d ", x);
                    printf("%d\n", F);
                });
                break;
            }
        }
        if(S == 0) printf("-1\n");
    }
}