Submission #872931

#	Time	Username	Problem	Language	Result	Execution time	Memory
872931		Ghulam_Junaid	Pipes (CEOI15_pipes)	C++17	10 / 100	1445 ms	65536 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int par1[N], par2[N], h[N], mnh[N];
bool vis[N];
vector<int> g[N];
vector<pair<int, int>> bridges;

int root1(int v){
    return (par1[v] == -1 ? v : par1[v] = root1(par1[v]));
}

int root2(int v){
    return (par2[v] == -1 ? v : par2[v] = root2(par2[v]));
}

void merge1(int u, int v){
    // cout << "merge1 : " << u << " " << v << endl;
    
    int r1 = root1(v);
    int r2 = root1(u);

    par1[r1] = r2;

    g[v].push_back(u);
    g[u].push_back(v);
}

void merge2(int u, int v){
    int r1 = root2(u);
    int r2 = root2(v);

    if (r1 == r2)
        return;

    par2[r1] = r2;

    g[v].push_back(u);
    g[u].push_back(v);
}

void dfs(int v, int p = -1){
    // cout << v << endl;
    vis[v] = 1;
    mnh[v] = h[v];
    for (int u : g[v]){
        // cout << v << " -- " << u << endl;
        if (vis[u]){
            if (u != p)
                mnh[v] = min(mnh[v], h[u]);
            continue;
        }

        h[u] = h[v] + 1;
        dfs(u, v);
        mnh[v] = min(mnh[v], mnh[u]);

        // cout << u << " : " << mnh[u] << endl;
        if (mnh[u] >= h[u])
            bridges.push_back({v, u});
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i=1; i<=n; i++)
        par1[i] = par2[i] = -1;

    for (int i=0; i<m; i++){
        int u, v;
        scanf("%d %d", &u, &v);

        g[u].push_back(v);
        g[v].push_back(u);

        // if (root1(u) != root1(v))
        //     merge1(u, v);
        // else if (root2(u) != root2(v))
        //     merge2(u, v);
    }

    // cout << " ----------- \n";
    // for (int v = 1; v <= n; v++)
    //     for (int u : g[v])
    //         if (v < u)
    //         cout << v << " " << u << endl;
    // cout << " ----------- \n";

    for (int v = 1; v <= n; v++){
        if (!vis[v]){
            // cout << "---------------\n";
            dfs(v);
        }
    }

    for (auto [u, v] : bridges)
        printf("%d %d\n", u, v);
}

/*

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int par1[N], par2[N], h[N], mnh[N];
bool vis[N];
vector<int> g[N];
vector<pair<int, int>> bridges;

int root1(int v){
    return (par1[v] == -1 ? v : par1[v] = root1(par1[v]));
}

int root2(int v){
    return (par2[v] == -1 ? v : par2[v] = root2(par2[v]));
}

void merge1(int u, int v){    
    int r1 = root1(v);
    int r2 = root1(u);

    par1[r1] = r2;

    g[v].push_back(u);
    g[u].push_back(v);
}

void merge2(int u, int v){
    int r1 = root2(u);
    int r2 = root2(v);

    if (r1 == r2)
        return;

    par2[r1] = r2;

    g[v].push_back(u);
    g[u].push_back(v);
}

void dfs(int v, int p = -1){
    vis[v] = 1;
    mnh[v] = h[v];
    for (int u : g[v]){
        if (vis[u]){
            if (u != p)
                mnh[v] = min(mnh[v], h[u]);
            continue;
        }

        h[u] = h[v] + 1;
        dfs(u, v);
        mnh[v] = min(mnh[v], mnh[u]);

        if (mnh[u] >= h[u])
            bridges.push_back({u, v});
    }
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i=1; i<=n; i++)
        par1[i] = par2[i] = -1;

    for (int i=0; i<m; i++){
        int u, v;
        scanf("%d%d", &u, &v);

        if (root1(u) == root1(v))
            merge2(u, v);
        else
            merge1(u, v);
    }

    for (int v = 1; v <= n; v++)
        if (!vis[v])
            dfs(v);

    for (auto [u, v] : bridges)
        printf("%d %d\n", u, v);
}

*/


/*
80 171
76 13
1 71
13 34
17 31
40 26
39 18
19 26
56 21
18 74
26 33
18 32
6 20
22 50
4 5
61 54
36 15
29 15
30 51
38 10
31 66
35 70
29 50
6 7
75 47
18 46
45 73
31 10
34 20
4 25
73 24
69 6
73 17
20 6
37 30
43 71
4 67
1 2
62 20
72 44
38 59
53 46
49 70
31 38
40 33
63 21
54 40
49 77
45 17
50 64
63 56
20 69
69 20
9 44
27 6
58 51
46 60
23 9
28 42
44 65
23 9
36 29
15 71
76 55
17 73
54 68
8 1
4 18
72 44
39 18
54 40
28 14
22 71
48 20
32 11
39 18
20 62
45 59
1 43
58 2
17 52
63 77
25 39
55 27
7 63
3 4
8 50
65 37
34 20
26 61
40 19
77 21
44 51
23 51
19 26
21 56
60 25
18 46
42 14
52 24
4 11
24 59
68 47
51 58
7 35
77 49
2 3
24 66
33 54
31 73
69 20
58 16
44 2
6 62
66 24
17 73
12 19
10 73
77 63
38 52
27 41
59 38
6 55
20 6
38 59
60 39
51 44
49 7
2 9
24 73
24 17
46 39
38 45
5 6
35 49
71 50
64 8
16 2
56 7
62 20
1 64
29 22
19 47
12 19
68 54
10 17
50 43
22 71
22 1
66 24
16 37
8 64
41 48
3 59
5 47
8 71
53 60
25 4
21 56
70 49
4 32
56 28
69 55
43 22
3 59
39 32
70 14
19 68
48 62
44 37
73 66
42 14
*/

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10