|
|
2 1 2 Ответ: 1 Этот тест может быть крайним случаем в вашем решении так как уже на такой тест и схожие: 3 2 2 3 Ответ: 2 Edited by author 05.05.2021 06:45 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> const long long mod=1000000007; const int nmax=200; int n,m,t,p; long long v[nmax],fact[nmax],step[nmax]; bool used[nmax]; bool a[nmax][nmax]; long long ans; void DFS(int v) { for(int j=1;j<=n;j++) { if(a[v][j] && !used[j]) { t++; used[j]=true; DFS(j); } } } bool FindCycle(int v,int pr) { bool f=false; for(int j=1;j<=n;j++) { if(a[v][j] && j!=pr) { if(used[j]) return true; else { used[j]=true; t++; f=f | FindCycle(j,v); } } } return f; } void main() { scanf("%d%d\n",&n,&m);
if(n<=2) { printf("1"); return; }
fact[0]=1; for(int i=1;i<=n;i++) fact[i]=fact[i-1]*((long long)i) % mod;
for(int i=1;i<=n;i++) step[i]=0;
for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) a[i][j]=false; }
for(int i=1;i<=m;i++) { scanf("%d\n",&t); if(!a[i][t]) { a[i][t]=a[t][i]=true; step[i]++; step[t]++;
} }
p=1; while(p<=n && step[p]<=2) p++; if(p<=n) { printf("0"); return; }
for(int i=1;i<=n;i++) used[i]=false;
for(int i=1;i<=n;i++) { if(!used[i]) { used[i]=true; t=1; if(FindCycle(i,-1)) { if(t<n) { printf("0"); return; } if(t==n) { printf("2"); return; } }
} }
for(int i=1;i<=n;i++) used[i]=false; p=0; ans=1; for(int i=1;i<=n;i++) { if(!used[i]) { p++; t=1; used[i]=true; DFS(i); if(t>1) t=2; ans*=((long long)t) % mod; } } ans=ans*fact[p-1] % mod; while(ans<0) ans+=mod; printf("%lld",ans); } Test #9 is the first test with N = 100, and it's also the first with M = 100. I've generated 2k+ random tests with those parameters but got no difference between programs, so i guess it should be a quite specific test. Anyways, the right answer to that one is 950M ± 10M, and yours is 580M ± 10M. В-общем,я в своём репертуаре. ТОТ ЖЕ ГОВНОКОД, но на ПАСКАЛЕ, дал АС! P.S. Glad to see you, Jane Soboleva!!! Oh, i guess it was something syntax-specific then, like in a certain place there goes a wrong order of operations or something like that... P.S. Glad to see you, Jane Soboleva!!! <3 Wa9. Хотелось бы несколько наглядных тестов или указание на ошибку в решении. Решение: 1)n<=2 => ans=1 2)n>=3; если есть вершина степени >=3 => ans=0 иначе в графе (неориентированном) есть либо циклы, либо цепи, причём они не пересекаются (т.е. от цикла ни одна цепь не отходит) а)пусть найден некоторый цикл если его длина = n => ans=2 иначе ans=0 б)циклов нет пусть p-общее число цепей в графе, len(i)-длина i цепи если len(i)>2 то положим len(i)=2 => ans=len(1)*len(2)*...*len(p)*(p-1)! Edited by author 19.09.2016 19:13 Edited by author 19.09.2016 19:34 Edited by author 29.10.2016 23:21 Test: 2 1 2 answer: 1 Maybe your answer is 2? =) Edited by author 02.09.2013 03:44 Edited by author 02.09.2013 03:46 Edited by author 22.06.2013 14:08 |
|
|