ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 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
Posted by Anton R. Dimitrov 16 Aug 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;
}