网站开发三层架构,网站建设与应用 教案,网站前端跟后端怎么做,网络隐私安全luogu 1477 [NOI2008] 假面舞会 容易发现#xff1a; 如果图中没有环#xff0c;那么面具种数一定是所有联通块内最长链之和#xff0c;最少为 \(3\) 。 如果有环#xff0c;则面具种数一定是所有环的大小的最大公约数。 那么只要求出每一个联通块内的最长链与环即可。 由… luogu 1477 [NOI2008] 假面舞会 容易发现 如果图中没有环那么面具种数一定是所有联通块内最长链之和最少为 \(3\) 。 如果有环则面具种数一定是所有环的大小的最大公约数。 那么只要求出每一个联通块内的最长链与环即可。 由于是有向边难以通过有向边判断联通块因此考虑建立一个反向边。将原来的边边权设为 \(1\) 反向边边权设为 \(-1\) 。 在 \(\text{dfs}\) 时记录这个联通块内最大、最小的 \(dep\) 相减即为最长链。而如果遇到了已经访问过的点那么一定有环。 #includebits/stdc.h
using namespace std;
#define infll 0x7f7f7f7f7f7f7f7fll
#define inf 0x3f3f3f3f
#define Maxn 100005
#define Maxm 1000005
typedef long long ll;
inline int rd()
{int x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
int gcd(int x,int y){ return (y0)?x:gcd(y,x%y); }
int n,m,tot,ans1,ans2,maxx,minn;
int dfn[Maxn],hea[Maxn],nex[Maxm1],ver[Maxm1],edg[Maxm1];
bool vis[Maxn];
void add(int x,int y,int d){ ver[tot]y,nex[tot]hea[x],hea[x]tot,edg[tot]d; }
void dfs(int x,int Dep)
{if(vis[x]) { ans1gcd(ans1,abs(Dep-dfn[x])); return; }dfn[x]Dep,vis[x]true;maxxmax(maxx,dfn[x]),minnmin(minn,dfn[x]);for(int ihea[x];i;inex[i]) dfs(ver[i],Depedg[i]);
}
int main()
{nrd(),mrd();for(int i1,x,y;im;i) xrd(),yrd(),add(x,y,1),add(y,x,-1);for(int i1;in;i) if(!vis[i])maxx-inf,minninf,dfs(i,0),ans2maxx-minn1;if(ans1){if(ans13) printf(-1 -1\n);else{for(int i3;ians1;i)if(ans1%i0) { printf(%d %d\n,ans1,i); break; }}}else{if(ans23) printf(-1 -1\n);else printf(%d 3\n,ans2);}return 0;
}
