3 3
2
3
1

Ans: 2

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);
}

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