# 【题解】 P8287 「DAOI R1」Flame()-其他

## 【题解】 P8287 「DAOI R1」Flame()

### AC Code（Tarjan）

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
int stk[1000005],top,col[1000005];
bool mark[1000005],vis[1000005],fl;
struct node{
int to,nxt;
}e[4000005];
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
}
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
}
}
void init(){
for(int i=1;i<=n;i++) dfn[i]=low[i]=col[i]=0,vis[i]=0;
tot=timer=0,fl=0;
}
void tarjan(int x,int fa){
if(fl) return ;
dfn[x]=low[x]=++timer;
int tmp=e[i].to;
if(tmp==fa) continue;
if(!dfn[tmp]){
tarjan(tmp,x);
if(fl) return ;
low[x]=min(low[x],low[tmp]);
}
else low[x]=min(low[x],dfn[tmp]);
}
if(low[x]<dfn[x]){
fl=1;
return ;
}
}
bool check(int mid){
init();
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
}
for(int i=1;i<=n;i++) if(!dfn[i]) top=0,tarjan(i,0);
return fl;
}
signed main(){
for(int i=1;i<=m;i++){
}
for(int i=1;i<=n;i++) dis[i]=1e9;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}


### AC Code（DSU）

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
bool vis[1000005];
struct DSU{
int fa[1000005];
void init(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
}
bool query(int x,int y){
return find(x)==find(y);
}
}dsu;
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
}
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
}
bool check(int mid){
dsu.init(n);
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
if(dsu.query(u[i],v[i])) return 1;
else dsu.merge(u[i],v[i]);
}
return 0;
}
signed main(){
for(int i=1;i<=m;i++){
}
for(int i=1;i<=n;i++) dis[i]=1e9;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}

————————

### AC Code（Tarjan）

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
int stk[1000005],top,col[1000005];
bool mark[1000005],vis[1000005],fl;
struct node{
int to,nxt;
}e[4000005];
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
}
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
}
}
void init(){
for(int i=1;i<=n;i++) dfn[i]=low[i]=col[i]=0,vis[i]=0;
tot=timer=0,fl=0;
}
void tarjan(int x,int fa){
if(fl) return ;
dfn[x]=low[x]=++timer;
int tmp=e[i].to;
if(tmp==fa) continue;
if(!dfn[tmp]){
tarjan(tmp,x);
if(fl) return ;
low[x]=min(low[x],low[tmp]);
}
else low[x]=min(low[x],dfn[tmp]);
}
if(low[x]<dfn[x]){
fl=1;
return ;
}
}
bool check(int mid){
init();
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
}
for(int i=1;i<=n;i++) if(!dfn[i]) top=0,tarjan(i,0);
return fl;
}
signed main(){
for(int i=1;i<=m;i++){
}
for(int i=1;i<=n;i++) dis[i]=1e9;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}


### AC Code（DSU）

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
bool vis[1000005];
struct DSU{
int fa[1000005];
void init(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
}
bool query(int x,int y){
return find(x)==find(y);
}
}dsu;
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
}
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
}
bool check(int mid){
dsu.init(n);
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
if(dsu.query(u[i],v[i])) return 1;
else dsu.merge(u[i],v[i]);
}
return 0;
}
signed main(){
for(int i=1;i<=m;i++){
}
for(int i=1;i<=n;i++) dis[i]=1e9;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}