ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1077. Travelling Tours

What's wrong with this problem? I always get WA even when I tried some of the solutions offered in the forum
Послано Anton R. Dimitrov 16 авг 2003 19:27
My solution is :

#include <stdio.h>

#define MAX             205
#define INF             2000000000

int n,m;
int nasl[MAX][MAX];
int brn[MAX];
int vis[MAX];
int par[MAX];
int tree[MAX][MAX];
//short used[MAX][MAX];
int matr[MAX][MAX];
int brc;
//short cycles[MAX*MAX][3];  // nachalo, kraj, naj-malko izpolzvanoto
rebro
int from,toFind;
int count;
int bri,bri2;
int li[MAX*MAX],li2[MAX*MAX];


void DFS(int num)
{
  int i;

  vis[num] = 1;

  for(i=0;i<brn[num];i++)
  {
    if(!vis[nasl[num][i]])
    {
      tree[num][nasl[num][i]] = 1;
      tree[nasl[num][i]][num] = 1;
      par[nasl[num][i]] = num;
      DFS(nasl[num][i]);
    }
  }

}

void DFSW()
{
  int i;

  for(i=0;i<n;i++)
    if(!vis[i])
    {
      par[i] = -1;
      DFS(i);
    }
}


int main()
{
  int i,i2,i3,cur;
  int a1,a2;

//  freopen("1077.in","r",stdin);

  scanf("%d %d",&n,&m);

  for(i=0;i<=n;i++)
  {
    vis[i] = 0;
    brn[i] = 0;
    for(i2=0;i2<n;i2++)
    {
      tree[i][i2] = 0;
    }
  }


  for(i=0;i<m;i++)
  {
    scanf("%d %d",&a1,&a2);
    nasl[a1-1][brn[a1-1]++] = a2-1;
    nasl[a2-1][brn[a2-1]++] = a1-1;
    matr[a1-1][a2-1] = matr[a2-1][a1-1] = 1;
  }

  DFSW();
//  DFS(0);

  count = 0;

  for(i=0;i<n;i++)
    for(i2=i+1;i2<n;i2++)
      if(matr[i][i2]==1 && tree[i][i2]==0)
        count++;

  printf("%d\n",count);

  for(i=0;i<n;i++)
    for(i2=i+1;i2<n;i2++)
      if(matr[i][i2]==1 && tree[i][i2]==0)
      {
        bri = 0;
        bri2 = 0;

        cur = i;

        while(cur!=-1)
        {
          li[bri++] = cur;
          cur = par[cur];
        }

        cur = i2;

        while(cur!=-1)
        {
          li2[bri2++] = cur;
          cur = par[cur];
        }

        bri--;
        bri2--;

        while(li[bri]==li2[bri2])
        {
          bri--;
          bri2--;
        }

        printf("%d ",bri+2+bri2+1);

        for(i3=0;i3<=bri+1;i3++)
          printf("%d ",li[i3]+1);

        for(i3=bri2;i3>=0;i3--)
          printf("%d ",li2[i3]+1);

        printf("\n");


      }



  return 0;
}