let N be the node num of the graph.
so why the maximum cycle number is M-N+1?
where M is the edge num.

please...

I found the problem statement a little hard to understand, and I want to make some clarifications for anyone who is having difficulties.

1. We are looking for the maximum number of cycles such that each of these chosen cycles has at least one edge which is not included in any other chosen cycle.

2. The graph is not necessarily connected.

I originally thought that we had to choose the maximum number of cycles which have at least one edge not included in all other chosen cycles. Hope this can help people.

Awesome English...

One of my AC solutions will crash on test

200 3
1 200
200 199
199 1

and on many other like this one.

(I'm never using vertex #200 in this solution)

I got WA1 so I made some debug and discovered that test 1 has N = 136 (with lines like if (N == 136) while(1);
The problem with code was that I was using char instead of unsigned char :)

Check this test:
136 6
130 132
136 135
135 130
130 133
133 134
133 135

One good answer should be
1
3 130 133 135

Edited by author 24.10.2004 08:18

Edited by author 24.10.2004 08:19

CODE IS HERE;
#include "stdio.h"
#include "string.h"
long a[401][401];
long n,h,t;
long i,j,m;
int  c[500];
int  p[500];

long count=0;
void bfs(int i)
{
    int k;
    for(k=1;k<=n;k++)
    {
        if(c[k]==0)
        {
            if(a[i][k]==1)
              {
                a[i][k]=0;
                a[k][i]=0;
                c[k]=1;
                p[k]=i;
                bfs(k);
               }
        }
    }

}


void path(int a1,int a2)
{
    int q[500];
    int i=0;
    while(1)
    {
        q[i]=a2;
        i++;
        a2=p[a2];
        if(a2==a1) break;
    }
    printf("%d",i+1);
    printf(" %d",a1);
    while(i>0)
    {
        printf(" %d",q[i-1]);
        i--;
    }
    printf("\n");


}



void main()
{
    for(i=0;i<401;i++)
        for(j=0;j<401;j++)
            a[i][j]=0;
    scanf("%ld %ld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%ld %ld",&h,&t);
            a[h][t]=1;
            a[t][h]=1;
    }
    for(i=1;i<=n;i++)
        c[i]=0;

    c[1]=1;
    bfs(1);

    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
            if(a[i][j]==1)
            {
                count++;
            }
    }
    printf("%ld\n",count);
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
            if(a[i][j]==1)
            {
                path(i,j);
            }
    }

}

My answer for the sample is
3
3 1 4 2
3 2 3 4
4 1 3 4 2
or
3
3 1 4 2
4 1 3 4 2
3 2 3 4
Can anyone give me the 1st test?

I have no idea what's wrong...
I am using DFS (something like euler-cycle detection); checking for self-loop edges; output format is right, tho it returns little bit different for sample test:
3
3 1 2 4
4 1 2 4 3
3 2 4 3

Please, any ideas about wa#1?

oh, i forgot to add that i am doing dfs for every connected component separately!

Edited by author 15.06.2010 03:05

For example:
7 10
1 2
2 3
2 4
2 5
3 5
4 5
5 6
5 7
6 7
1 7
At first the DFS procedure find the loop:
(1,2,3,5,6,7,1),then it'll find (1,2,3,5,7,1).
and next,no loop with unused edge will be found!?!
In fact,the maximum T is 3(it's obvious),but use greedy
method + DFS the number of T only reach 2.
Unless we regulated the order of search
(it means DFS can't be right!),otherwise we have to
delete a found loop to let more loop to have unused
edge,then how to make the regulations?

why WA2??
program ural;
var n,a,b,y:byte;
    m,i,z,r:integer;
    h,g:array[1..200]of integer;
    t:array[1..32767]of byte;
    l:array[1..32767]of integer;
    p,q:array[1..32767]of boolean;
    s:array[1..200]of byte;
    k:array[1..400]of integer;
    o:array[1..400]of byte;
    u:array[1..200]of boolean;
    x:boolean;
procedure search(d:byte);
var r:integer;
  begin
    u[d]:=true;
    r:=h[d];
    while r<>0 do
      begin
        if u[t[r]]=false then
          begin
            inc(y);
            k[y]:=g[d];
            g[d]:=y;
            o[y]:=t[r];
            inc(y);
            k[y]:=g[t[r]];
            g[t[r]]:=y;
            o[y]:=d;
            p[r]:=true;
            if q[r] then
              p[r+1]:=true
            else
              p[r-1]:=true;
            search(t[r]);
          end;
        r:=l[r];
      end;
  end;
procedure track(v,d:byte);
var r:byte;
  begin
    if d=i then
      begin
        write(v,' ');
        for r:=1 to v-1 do
          write(s[r],' ');
        writeln(d);
        x:=true;
        exit;
      end;
    u[d]:=true;
    s[v]:=d;
    r:=g[d];
    while r<>0 do
      begin
        if u[o[r]]=false then
          track(v+1,o[r]);
        if x then
          exit;
        r:=k[r];
      end;
  end;
begin
  assign(input,'travel.in');
  assign(output,'travel.out');
  reset(input);
  rewrite(output);
  readln(n,m);
  for i:=1 to m do
    begin
      readln(a,b);
      inc(r);
      l[r]:=h[a];
      h[a]:=r;
      t[r]:=b;
      q[r]:=true;
      inc(r);
      l[r]:=h[b];
      h[b]:=r;
      t[r]:=a;
    end;
  z:=m-n;
  for i:=1 to n do
    if u[i]=false then
      begin
        inc(z);
        search(i);
      end;
  if z<=0 then
    begin
      writeln(0);
      exit;
    end
  else
    writeln(z);
  for i:=1 to n do
    begin
      r:=h[i];
      while r<>0 do
        begin
          if(q[r])and(p[r]=false)then
            begin
              x:=false;
              fillchar(u,sizeof(u),false);
              track(1,t[r]);
            end;
          r:=l[r];
        end;
    end;
end.

3
3 4 1 2
3 3 1 2
3 4 1 3

I wrote this program and think this is right. But I have WA#7. I tested my program by many my own test. And it gives correct answer in 100% cases. May be someone can give me a test. This is my prog:

[Code deleted by author]

Edited by author 28.08.2007 22:14

Does every tour always passes through the first city? There said, that it starts and ends in T1. Every tour in sample starts and ends in 1st vertice. So T1 = 1 or not?

Why so simple problem have so small percent of accepted??? Is there bad test? Or there is some nasty trick?

Here is my code:

var
 a : array [1..200,1..200] of byte;
 b,u,now : array [1..200] of boolean;
 p,c : array [1..200] of byte;
 v,i,j,n,m,x,y,t,r,k : longint;
procedure vvod;
begin
 read(n,m);
 for i := 1 to m do
 begin
  read(x,y);
  a[x,y] := 1;
  a[y,x] := 1;
 end; x := 0;
 fillchar(b,sizeof(b),true);
 fillchar(now,sizeof(now),true);
end;
procedure dfs(x : byte);
var
 i : byte;
begin
 now[x] := false;
 for i := 1 to n do
 if now[i] and (a[x,i] = 1) then
 begin
  p[i] := x;
  dfs(i);
 end;
end;
procedure cycle;
begin
 inc(t); k := 0;
 fillchar(u,sizeof(u),true);
 x := i;
 while (x <> 0) do
 begin
  u[x] := false; x := p[x];
 end;
 x := j;
 while (x <> 0) do
 begin
  inc(k); c[k] := x;
  if not(u[x]) then
  begin
   break; r := k;
  end;
  u[x] := false; x := p[x];
 end;
 y := i;
 while (y <> 0) and (y <> x) do
 begin
  inc(k); c[k] := x; x := p[x];
 end;
end;
procedure find;
begin
 for v := 1 to n do
 if now[v] then
 begin
  dfs(v); inc(x);
 end;
 writeln(m-n+x);
 for v := 1 to n do
 if b[v] then
 begin
  fillchar(now,sizeof(now),true);
  dfs(v);
  for i := 1 to n-1 do
  for j := i+1 to n do
  if not((p[i] = j) or (p[j] = i)) then
  begin
   if (a[i,j] = 1) and not(now[i]) and not(now[j]) then
   begin
    cycle;
    write(k);
    for x := 1 to r do write(' ',c[x]);
    for x := k downto r+1 do write(' ',c[x]);
    writeln;
   end;
  end;
  for i := 1 to n do
  if not(now[i]) then b[i] := false;
 end;
end;
begin
 vvod;
 find;
end.

my result is
3
3 1 2 4
4 1 2 4 3
3 2 4 3
with distinct roads
4 1
3 1
3 2
why wa?
did i understand something wrong?

Edited by author 13.05.2004 20:15

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

CONST
  NMax = 250;
VAR
  Route : ARRAY[1..NMax, 1..NMax] OF LongInt;
  Used : ARRAY[1..NMax] OF Boolean;
  Path : ARRAY[0..NMax] OF Integer;
  N, M, I, T, H, Count : LongInt;
  Found : Boolean;

  PROCEDURE DSF(Start, C : LongInt);
  VAR
    I : LongInt;
  BEGIN
    Used[C] := True;
    IF (Route[C, Start] = 2) THEN
      BEGIN
        Found := True;
        Used[C] := False;
        Exit;
      END;
    FOR I := 1 TO N DO
      IF (NOT Used[I]) AND (Route[C, I] = 2) THEN
        BEGIN
          Route[C, I] := 0;
          Route[I, C] := 0;
          DSF(Start, I);
          Route[C, I] := 2;
          Route[I, C] := 2;
          IF Found THEN Break;
        END;
    IF (NOT Found) THEN
      IF (Route[C, Start] = 1) THEN
        BEGIN
          Route[Start, C] := 2;
          Route[C, Start] := 2;
          Found := True;
        END;
    IF NOT Found THEN
      FOR I := 1 TO N DO
        IF (NOT Used[I]) AND (Route[C, I] = 1) THEN
          BEGIN
            Route[C, I] := 0;
            Route[I, C] := 0;
            DSF(Start, I);
            IF Found THEN
              BEGIN
                Route[C, I] := 2;
                Route[I, C] := 2;
                Break;
              END
            ELSE
              BEGIN
                Route[C, I] := 1;
                Route[I, C] := 1;
              END;
          END;
    Used[C] := False;
  END;

  PROCEDURE DSF2(Start, C, Size : LongInt);
  VAR
    I : LongInt;
  BEGIN
    Used[C] := True;
    IF (Route[C, Start] = 1) THEN
      BEGIN
        Found := True;
        Used[C] := False;
        Path[Size] := C;
        Path[0] := Size;
        Exit;
      END;
    FOR I := 1 TO N DO
      IF (NOT Used[I]) AND (Route[C, I] = 1) THEN
        BEGIN
          Route[C, I] := 0;
          Route[I, C] := 0;
          DSF2(Start, I, Size+1);
          Route[C, I] := 1;
          Route[I, C] := 1;
          IF Found THEN
            BEGIN
              Path[Size] := C;
              Break;
            END;
        END;
    IF (NOT Found) THEN
      IF (Route[C, Start] = 2) THEN
        BEGIN
          Route[Start, C] := 1;
          Route[C, Start] := 1;
          Path[Size] := C;
          Path[0] := Size;
          Found := True;
        END;
    IF NOT Found THEN
      FOR I := 1 TO N DO
        IF (NOT Used[I]) AND (Route[C, I] = 2) THEN
          BEGIN
            Route[C, I] := 0;
            Route[I, C] := 0;
            DSF2(Start, I, Size+1);
            IF Found THEN
              BEGIN
                Route[C, I] := 1;
                Route[I, C] := 1;
                Path[Size] := C;
                Break;
              END
            ELSE
              BEGIN
                Route[C, I] := 2;
                Route[I, C] := 2;
              END;
          END;
    Used[C] := False;
  END;

BEGIN
  FillChar(Route, SizeOf(Route), 0);
  FillChar(Used, SizeOf(Used), False);
  ReadLn(N, M);
  FOR I := 1 TO M DO
    BEGIN
      ReadLn(T, H);
      Route[T, H] := 1;
      Route[H, T] := 1;
    END;
  Count := 0;
  FOR T := 1 TO N DO
    FOR
    H := 1 TO N DO
      IF Route[T, H] = 1 THEN
        BEGIN
          Used[T] := True;
          Route[T, H] := 0;
          Route[H, T] := 0;
          Found := False;
          DSF(T, H);
          IF Found THEN
            BEGIN
              Route[T, H] := 2;
              Route[H, T] := 2;
              Inc(Count);
            END
          ELSE
            BEGIN
              Route[T, H] := 1;
              Route[H, T] := 1;
            END;
          Used[T] := False;
        END;
  WriteLn(Count);
  IF Count <> 0 THEN
    BEGIN
      FOR T := 1 TO N DO
        FOR H := 1 TO N DO
          IF Route[T, H] = 2 THEN
            BEGIN
              Used[T] := True;
              Route[T, H] := 0;
              Route[H, T] := 0;
              Found := False;

I think my method is right, but it always gets WR!
Thank u!


#include "stdio.h"

int n, m, M[201][201];
int B[201][2], F[201];

void Init() {
    int i, j, k;

    scanf("%d %d",&n,&m);
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++) M[i][j] = 0;

    for (k=0; k<m; k++) {
        scanf("%d %d",&i,&j);
        if (i!=j) M[i][j] = M[j][i] = 1;
    }
}

void CT(int num, int father, int level) {
    int i;
    F[num] = 1;
    B[num][0] = father; B[num][1] = level;
    for (i=1; i<=n; i++)
        if (!F[i] && M[num][i]) {
            M[num][i] = M[i][num] = 0;
            CT(i, num, level+1);
        }
}

void CreateTree() {
    int i;

    for (i=1; i<=n; i++) F[i] = 0;

/*    for (i=1; i<=n; i++)
        if (!F[i]) {
            Pth[0] = i; nail = head = 0;
            B[i][0] = 0; B[i][1] = 1; F[i] = 1;
            while (head<=nail) {
                j = Pth[head]; head++;
                for (k=1; k<=n; k++)
                    if (!F[k] && M[j][k]) {
                        nail++; Pth[nail] = k;
                        B[k][0] = j; B[k][1]
= B[j][1] + 1;
                        F[k] = 1;
                        M[j][k] = M[k][j] = 0;
                    }
            }
        }*/
    for (i=1; i<=n; i++) {
        if (!F[i]) CT(i, 0, 1);
    }
/*    for (i=1; i<=n; i++) printf("%d %d\n",B[i][0],B[i][1]);*/
}

void Caculate() {
    int total, i, j;
    int Pth[2][201], l[2];

    for (i=1, total=0; i<=n; i++)
        for (j=1; j<=n; j++)
            if (M[i][j]==1) {
                total++;
                M[i][j] = M[j][i] = 2;
            }
    printf("%d\n",total);

    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (M[i][j]==2) {
                M[i][j] = M[j][i] = 0;
                l[0] = l[1] = 0;
                Pth[0][0] = i;
                Pth[1][0] = j;

                while (Pth[0][l[0]]!=Pth[1][l[1]])
                    if (B[Pth[0][l[0]]][1]==B[Pth
[1][l[1]]][1]) {
                        l[0]++; Pth[0][l[0]]
= B[Pth[0][l[0]-1]][0];
                        l[1]++; Pth[1][l[1]]
= B[Pth[1][l[1]-1]][0];
                    }
                    else if (B[Pth[0][l[0]]][1]>B
[Pth[1][l[1]]][1]) {
                        l[0]++; Pth[0][l[0]]
= B[Pth[0][l[0]-1]][0];
                    }
                    else {
                        l[1]++; Pth[1][l[1]]
= B[Pth[1][l[1]-1]][0];
                    }

                printf("%d",l[0]+l[1]+1);
                for (i=0; i<=l[0]; i++) printf(" %
d",Pth[0][i]);
                for (i=l[1]-1; i>=0; i--) printf(" %
d",Pth[1][i]);
                printf("\n");
            }

}

main() {
    Init();
    CreateTree();
    Caculate();
}