[SHOI2014]神奇化合物解题报告

本文主要是介绍[SHOI2014]神奇化合物解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做题的时候一上来就把时间复杂度算错了。。DFS的时间复杂度是O(n+m),我竟然给算成O(n)了！

想过来以后还是比较简单的，观察到m很大但q很小，所以可以将图删成树以得到O(q(n+q))的时间复杂度，至于UFS什么的，用不用都行。

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
char * ptr=(char *)malloc(10000000);
int fa[5001],n[50000],p[5001],s[50000],qc[10000],qa[10000],qb[10000],tot=1;
bool g[5001][5001],pg[5001][5001],flag[5001];
struct ES{int a,b;
}e[200000];
inline void in(int &x){while(*ptr<'0'||*ptr>'9')++ptr;x=0;while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void add(int x,int y){n[tot]=p[x],p[x]=tot,s[tot++]=y;
}
inline void dfs(int x,int ftr){flag[x]=0;fa[x]=ftr;for(int i=p[x];i;i=n[i])if(flag[s[i]]&&g[x][s[i]]){dfs(s[i],ftr);}
}
inline int 

这篇关于[SHOI2014]神奇化合物解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---