제출 #1203873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203873		12345678	Pipes (CEOI15_pipes)	C++20	100 / 100	625 ms	16236 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, m, u, v, dsu1[nx], dsu2[nx], t, rt;
vector<pair<int ,int>> d[nx];

int find1(int x)
{
    if (dsu1[x]==x) return x;
    return dsu1[x]=find1(dsu1[x]);
}

int find2(int x)
{
    if (dsu2[x]==x) return x;
    return dsu2[x]=find2(dsu2[x]);
}

void dfs(int u, int p, int pidx)
{
    dsu1[u]=dsu2[u]=++t;
    for (auto [v, idx]:d[u])
    {
        if (idx==pidx) continue;
        if (!dsu1[v]) dfs(v, u, idx), dsu2[u]=min(dsu2[u], dsu2[v]);
        else dsu2[u]=min(dsu2[u], dsu1[v]);
    }
    if (dsu1[u]==dsu2[u]&&u!=rt) cout<<u<<' '<<p<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n ;i++) dsu1[i]=dsu2[i]=i;
    for (int i=1; i<=m; i++)
    {
        cin>>u>>v;
        if (find1(u)!=find1(v))
        {
            dsu1[find1(u)]=find1(v);
            d[u].push_back({v, i});
            d[v].push_back({u, i});
        }
        else if (find2(u)!=find2(v))
        {
            dsu2[find2(u)]=find2(v);
            d[u].push_back({v, i});
            d[v].push_back({u, i});
        }
    }
    for (int i=1; i<=n; i++) dsu1[i]=dsu2[i]=0;
    for (int i=1; i<=n; i++) if (!dsu1[i]) rt=i, dfs(i, i, -1);
}

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