제출 #1150421

#제출 시각아이디문제언어결과실행 시간메모리
1150421SSSMPipes (CEOI15_pipes)C++20
100 / 100
1842 ms15716 KiB
#include <bits/stdc++.h>
 
/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/
 
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
 
#define F first
#define S second
#define pb push_back
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
#define SZ(a) (ll)a.size()
 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=31, sq=65;
 
ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

int n, m, par0[maxn], par1[maxn], sz0[maxn], sz1[maxn], h[maxn], low[maxn];
vector<pii> g[maxn];

void DSU()
{
    for(int i=0;i<maxn;i++) {
        par0[i]=par1[i]=i;
        sz0[i]=sz1[i]=1;
    }
}

int Find0(int v) {return par0[v]==v?v:par0[v]=Find0(par0[v]);}
int Find1(int v) {return par1[v]==v?v:par1[v]=Find1(par1[v]);}

bool Union(int v, int u)
{
    int v0, u0;
    if((v0=Find0(v))==(u0=Find0(u))){
        int v1, u1;
        if((v1=Find1(v))==(u1=Find1(u))) return 0;
        if(sz1[v1]<sz1[u1]) swap(v1, u1);
        par1[u1]=v1;
        sz1[v1]+=sz1[u1];
        return 1;
    }

    if(sz0[v0]<sz0[u0]) swap(v0, u0);
    par0[u0]=v0;
    sz0[v0]+=sz0[u0];
    return 1;
}

void DFS(int v, int p=0, int lst=0)
{
    h[v]=h[p]+1;
    low[v]=h[v];
    for(auto [u, id]:g[v])
    {
        if(id==lst) continue;
        if(!h[u]) DFS(u, v, id);
        low[v]=min(low[v], low[u]);
    }
    if(low[v]==h[v] && p!=0)
    {
        cout<<v<<" "<<p<<"\n";
    }
}

int main() {

    cin>>n>>m;
    DSU();
    for(int i=1;i<=m;i++)
    {
        int v, u;
        cin>>v>>u;
        if(Union(v, u)){
            g[v].pb({u, i});
            g[u].pb({v, i});
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(!h[i]) DFS(i);
    }

	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...