Submission #1347612

#TimeUsernameProblemLanguageResultExecution timeMemory
1347612tung04885Pipes (CEOI15_pipes)C++20
100 / 100
464 ms14716 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define LOG 17
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;

struct EDGE
{
    int u,v;

    int other(int x)
    {
        assert(x==u||x==v);
        return u+v-x;
    }
};

struct DSU
{
    vector<int> par;

    DSU(int n=0)
    {
        par.resize(n+1);

        for(int i=1;i<=n;i++) par[i]=i;
    }

    int find_set(int a)
    {
        if(a==par[a]) return a;

        int p=find_set(par[a]);

        par[a]=p;

        return p;
    }

    bool union_set(int a,int b)
    {
        a=find_set(a);
        b=find_set(b);

        if(b!=a)
        {
            par[b]=a;
            return 1;
        }

        return 0;
    }
};

EDGE edge[2*MAX];
int n,m;
vector<int> adj[MAX];
DSU dsu[2];

int low[MAX],num[MAX],dem=0;
bool used[2*MAX]={},bridge[2*MAX]={};

void dfs(int u)
{
    num[u]=++dem;
    low[u]=n+1;

    for(int id:adj[u]) if(!used[id])
    {
        used[id]=1;

        int v=edge[id].other(u);

        if(num[v]==0)
        {
            dfs(v);

            minimize(low[u],low[v]);

            if(low[v]>num[u]) bridge[id]=1;
        }
        else minimize(low[u],num[v]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    cin>>n>>m;

    dsu[0]=dsu[1]=DSU(n);

    int cnt=0;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;

        if(dsu[0].union_set(u,v)||dsu[1].union_set(u,v))
        {
            edge[++cnt]={u,v};

            adj[u].push_back(cnt);
            adj[v].push_back(cnt);
        }
    }

    for(int i=1;i<=n;i++) if(num[i]==0)
        dfs(i);

    for(int i=1;i<=cnt;i++) if(bridge[i]) cout<<edge[i].u<<' '<<edge[i].v<<'\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...