Atcoder 1918 駐車場 变删点为加点,并查集

文章目录

题意题解

题意

$略$.

题解

看到一个一个把点删掉,可以想到倒过来做,变删点为加点. 这样每次可以把每个点和它在图上的比它编号大的点连在同一个集合里. (编号小的点被删掉了). 如果它和$S$同父亲,想必它们是连通的. 这样就可做了.谢谢大家.

#include<bits/stdc++.h> //Ithea Myse Valgulious namespace chtholly{ typedef long long ll; #define re0 register int #define rel register ll #define rec register char #define gc getchar //#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++) #define pc putchar #define p32 pc(' ') #define pl puts("") /*By Citrus*/ char buf[1<<23],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1;char c=gc(); for (;!isdigit(c);c=gc()) f^=c=='-'; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return f?x:-x; } template <typename mitsuha> inline bool read(mitsuha &x){ x=0;int f=1;char c=gc(); for (;!isdigit(c)&&~c;c=gc()) f^=c=='-'; if (!~c) return 0; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return x=f?x:-x,1; } template <typename mitsuha> inline int write(mitsuha x){ if (!x) return 0&pc(48); if (x<0) pc('-'),x=-x; int bit[20],i,p=0; for (;x;x/=10) bit[++p]=x%10; for (i=p;i;--i) pc(bit[i]+48); return 0; } inline char fuhao(){ char c=gc(); for (;isspace(c);c=gc()); return c; } }using namespace chtholly; using namespace std; const int yuzu=2e5; typedef int fuko[yuzu|10]; namespace dsu{ fuko fa; void init(int n){for (int i=1;i<=n;++i) fa[i]=i;} int find(int x){return fa[x]^x?fa[x]=find(fa[x]):x;} int mg(int u,int v){return find(u)^find(v)?fa[find(u)]=find(v),1:0;} }using dsu::find; vector<int> lj[yuzu|10]; int main() { int i,n,m,u,v,s; read(n),read(m),read(s); dsu::init(n); for (i=1;i<=m;++i) u=read(),v=read(), lj[min(u,v)].push_back(max(u,v)); for (i=n;i;--i) { for (int p:lj[i]) dsu::mg(p,i); if (find(i)==find(s)) (*lj).push_back(i); } reverse((*lj).begin(),(*lj).end()); for (int p:*lj) write(p),pl; }