fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int n,m,Mod;
  29.  
  30. int begin[MAX],next[MAX*2],t[MAX*2],tot;
  31. int q[MAX],fac[MAX],lonely,down[MAX],up[MAX],in[MAX],fa[MAX];
  32. bool hash[MAX];
  33.  
  34. void add(int a,int b)
  35. {
  36. 	t[++tot]=b;
  37. 	next[tot]=begin[a];
  38. 	begin[a]=tot;
  39. }
  40.  
  41. int top;
  42. pair<int,int> toWork[MAX];
  43.  
  44. LL get()
  45. {
  46. 	int i;
  47. 	int numone=0,numtwo=0,numto=1;
  48. 	for(i=1;i<=top;++i)
  49. 	{
  50. 		int e=toWork[i].x;
  51. 		if(e==1)
  52. 			++numone;
  53. 		else
  54. 		{
  55. 			++numtwo;
  56. 			numto=toWork[i].y;
  57. 		}
  58. 	}
  59. 	if(numtwo>1)
  60. 		return 0;
  61. 	return (LL)fac[numone]*numto % Mod;
  62. }
  63.  
  64. LL BFS(int S)
  65. {
  66. 	int head,end,num=0,nume=0;
  67. 	head=end=1;
  68. 	q[end++]=S;
  69. 	hash[S]=true;
  70. 	while(head<end)
  71. 	{
  72. 		int u=q[head++];
  73. 		++num;
  74. 		for(int i=begin[u];i;i=next[i])
  75. 		{
  76. 			int v=t[i];
  77. 			++nume;
  78. 			if(!hash[v])
  79. 			{
  80. 				fa[v]=u;
  81. 				q[end++]=v;
  82. 				hash[v]=1;
  83. 			}
  84. 		}
  85. 	}
  86. 	if(2*(num-1)!=nume)
  87. 		return 0;
  88. 	if(num==1)
  89. 	{
  90. 		++lonely;
  91. 		return 1;
  92. 	}
  93. 	if(num==2)
  94. 		return 2;
  95. 	int i,j;
  96. 	down[0]=1;
  97. 	for(i=num;i>=1;--i)
  98. 	{
  99. 		int u=q[i];
  100. 		top=0;
  101. 		for(j=begin[u];j;j=next[j])
  102. 		{
  103. 			int v=t[j];
  104. 			if(fa[v]!=u)
  105. 				continue;
  106. 			toWork[++top]=mp(in[v],down[v]);
  107. 		}
  108. 		down[u]=get();
  109. 	}
  110. 	up[S]=1;
  111. 	REP(i,1,num)
  112. 	{
  113. 		int u=q[i];
  114. 		int numOne=0,numTwo=0,numto0=-1,numto2=-1;
  115. 		for(j=begin[u];j;j=next[j])
  116. 		{
  117. 			int v=t[j];
  118. 			if(fa[v]!=u)
  119. 				continue;
  120. 			if(in[v]==1)
  121. 				++numOne;
  122. 			else
  123. 			{
  124. 				++numTwo;
  125. 				if(numto0!=-1)
  126. 					numto2=down[v];
  127. 				else numto0=down[v];
  128. 			}
  129. 		}
  130. 		if(fa[u])
  131. 		{
  132. 			if(in[ fa[u] ]==1)
  133. 				++numOne;
  134. 			else
  135. 			{
  136. 				++numTwo;
  137. 				if(numto0!=-1)
  138. 					numto2=up[u];
  139. 				else numto0=up[u];
  140. 			}
  141. 		}
  142. 		for(j=begin[u];j;j=next[j])
  143. 		{
  144. 			int v=t[j];
  145. 			if(fa[v]!=u)
  146. 				continue;
  147. 			int nowOne=numOne;
  148. 			int nowTwo=numTwo;
  149. 			int nowTo=1;
  150. 			if(in[v]==1)
  151. 			{
  152. 				--nowOne;
  153. 				nowTo=numto0;
  154. 			}
  155. 			else
  156. 			{
  157. 				--nowTwo;
  158. 				if(numto0==down[v])
  159. 					nowTo=numto2;
  160. 				else nowTo=numto0;
  161. 			}
  162. 			if(nowTwo>1)
  163. 				up[v]=0;
  164. 			else up[v]=(LL)fac[nowOne]*abs(nowTo)%Mod;
  165. 		}
  166. 	}
  167. 	LL cc=0;
  168. 	REP(i,1,num)
  169. 	{
  170. 		int u=q[i];
  171. 		if(in[u]!=1)
  172. 			continue;
  173. 		top=0;
  174. 		for(j=begin[u];j;j=next[j])
  175. 		{
  176. 			int v=t[j];
  177. 			if(v==fa[u])
  178. 				;
  179. 			else toWork[++top]=mp(in[v],down[v]);
  180. 		}
  181. 		if(fa[u])
  182. 			toWork[++top]=mp(in[fa[u]],up[u]);
  183. 		LL tmp=get();
  184. 		cc+=tmp;
  185. 		if(cc>=Mod)
  186. 			cc-=Mod;
  187. 	}
  188. 	return cc*2 % Mod ;
  189. }
  190.  
  191. int main()
  192. {
  193. 	int i;
  194. 	int a,b;
  195. 	scanf("%d%d%d",&n,&m,&Mod);
  196. 	if(m>2*(n-1))
  197. 	{
  198. 		printf("0\n");
  199. 		return 0;
  200. 	}
  201. 	REP(i,1,m)
  202. 	{
  203. 		scanf("%d%d",&a,&b);
  204. 		++in[a];
  205. 		++in[b];
  206. 		add(a,b);
  207. 		add(b,a);
  208. 	}
  209. 	fac[0]=1;
  210. 	REP2(i,1,MAX)
  211. 		fac[i]=(LL)fac[i-1]*i % Mod;
  212. 	LL ans=1,tot=0;
  213. 	REP(i,1,n)
  214. 		if(!hash[i])
  215. 		{
  216. 			ans=ans* BFS(i) % Mod;
  217. 			if(begin[i])
  218. 				++tot;
  219. 		}
  220. 	ans=ans*fac[tot]%Mod;
  221. 	for(;lonely;lonely--)
  222. 		ans=ans* (n-lonely+2) % Mod;
  223. 	cout<<ans<<endl;
  224. 	return 0;
  225. }
  226.  
Success #stdin #stdout 0s 55064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/fssC0B
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!