That's my q.

Edited by author 20.12.2015 17:14

i used Fleury algorithm to find a Euler cycle

Edited by author 11.09.2015 12:47

Ridiculous! It's O(damn E)! AND I got rid of all the lists and used simple arrays instead. It just cannot get any faster than that...

Input
4 2
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0

Output
2 1
1 4
4 1
1 2
2 4
4 2

In C++ don't use cout and cin! Just use scanf(...) and printf(...).
Enjoy!

Edited by author 24.03.2012 00:22

Is my greedy algo correct?
On each step I choose an edge to vertex with the greatest out-degree.
I have WA 8.

If you code on Java use Thread to kill stack overflow

This my AC program. If I change one cycle, I get WA#3. WHY????

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static int[][] a;
    public static int[] d;
    public static int n;
    public static int top;
    public static int[] bol;

    public static void dfs(int v){
        bol[v] = 1;
        int i;
        for(i = 0;i < n;i ++){
            if(a[v][i] == 1){
                a[v][i] = 0;
                dfs(i);
            }
        }
        d[top] = v;
        top ++;
    }

    public static void solve()throws IOException {
         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        m --;
        a = new int[n][n];
        d = new int[n * n + 1];
        bol = new int[n];
        top = 0;
        int i, j;
        int res = 0;
        for(i = 0;i < n;i ++){
            st = new StringTokenizer(in.readLine());
            for(j = 0;j < n;j ++){
                a[i][j] = 1 - Integer.parseInt(st.nextToken());
                if(i == j)a[i][i] = 0;
                res += a[i][j];
            }
        }
        dfs(m);
        for(i = top - 1;i > 0;i --){
            System.out.println((d[i] + 1) + " " + (d[i - 1] + 1));
        }
    }

    public static void main(String[] args){
        new Thread(){
            public void run(){
                try{
                    solve();
                }catch(Exception e){

                }

            }
        }.start();

    }
}


This cycle.

for(i = top - 1;i > 0;i --){
            System.out.println((d[i] + 1) + " " + (d[i - 1] + 1));
        }

change to:

for(i = 0;i < top - 1;i ++){
            System.out.println((d[i] + 1) + " " + (d[i + 1] + 1));
        }

There was problem with this task, but now I get AC.

Edited by author 27.03.2007 00:05

Edited by author 27.03.2007 00:36

How can this algo get Stack overflow(test 12)?


#include <string>
#include <vector>
#include<iostream>
#include<queue>

using namespace std;

struct Pair{
    int a,b;
};

vector<int> res;
int n,s;
int a[1111][1111];

void dfs(int ver){
    for(int i=0;i<n;i++)
        if(ver!=i && !a[ver][i]){
            a[ver][i]=1;
            dfs(i);
        }
    res.push_back(ver);
}

int main(){

    cin>>n>>s;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];

    dfs(s-1);

    reverse(res.begin(),res.end());
    for(int i=1;i<res.size();i++)
        cout<<res[i-1]+1<<" "<<res[i]+1<<endl;

    system("pause");
    return 0;
}

if you got Wa 2 try it

4 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
without output


if you got MLE12
Not foget use dispose.

Gool Luck and Have fun.

I got WA on test 3.
Here is my code:


Program ex;
Const Rule              :Array [0..7] Of Integer
                        =(1,2,4,8,16,32,64,128);
Var G                   :Array [1..1001,0..125] Of Byte;
    Len,M               :Integer;
    St,Ar               :Array [1..32010] Of Integer;
    N,Be                :Integer;
Procedure Init;
Var P,Q,U               :Integer;
Begin
  Readln(N,Be);
  For P:=1 To N Do
    For Q:=1 To N Do Begin
      Read(U);
      If (U=0) And (P<>Q) Then Inc(G[P,(Q-1) Div 8],Rule[(Q-1) Mod 8]);
    End;
End;
Procedure Main;
Var I,J                 :Integer;
Begin
  M:=0;
  Len:=1;
  St[1]:=Be;
  Repeat
    I:=St[Len];
    J:=1;
    Repeat
      If G[I,(J-1) Div 8] And Rule[(J-1) Mod 8]>0 Then Break;
      Inc(J);
    Until J>N;
    If J<=N Then Begin
      Dec(G[I,(J-1) Div 8],Rule[(J-1) Mod 8]);
      Inc(Len);
      St[Len]:=J;
    End Else Begin
      Dec(Len);
      Inc(M);
      Ar[M]:=I;
    End;
  Until Len=0;
  If Ar[1]<>Be Then Begin
    Repeat
    Until False;
  End;
  For I:=1 To M-1 Do Writeln(Ar[I],' ',Ar[I+1]);
End;
Begin
  Init;
  Main;
End.

For sample input:

4 2
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0

I must find Eulerian cycle for such graph:

0 1 0 1
1 0 0 1
0 0 0 0
1 1 0 0

Is new graph correct or not?

Edited by author 01.11.2004 21:34

var
  g:array[1..1000,1..1000] of Boolean;
  i,j,n,a,k,s:smallint;
procedure find(i:smallint);
var
  j:smallint;
begin
  for j:=n downto 1 do
    if g[i,j] then
      begin
        g[i,j]:=false;
        find(j)
      end;
  if s<>0 then
    writeln(s,' ',i);
  s:=i;
end;
begin
  assign(input,'');
  reset(input);
  readln(n,a);
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(k);
        g[i,j]:=(k=0) and (i<>j)
      end;
  close(input);
  s:=0;
  find(a);
end.

If I put s in memory and write it in reverse order I get MLE on test 12:
var
  g:array[1..1000,1..1000] of Boolean;
  i,j,n,a,k,st:smallint;
  s:array[1..32000] of smallint;
procedure find(i:smallint);
var
  j:smallint;
begin
  for j:=n downto 1 do
    if g[i][j] then
      begin
        g[i][j]:=false;
        find(j)
      end;
  inc(st);
  s[st]:=i
end;
begin
  assign(input,'');
  reset(input);
  readln(n,a);
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(k);
        g[i][j]:=(k=0) and (i<>j)
      end;
  close(input);
  st:=0;
  find(a);
  for i:=st-1 downto 1 do
    writeln(s[i+1],' ',s[i]);
end.

Please help me solve either of this two problems.

#include <stdio.h>
#include <stdlib.h>

#define N 1050

#define setbit1(x,y) ( a[x][y >> 3] |=  (1 << (y & 7)) )
#define setbit0(x,y) ( a[x][y >> 3] &= ~(1 << (y & 7)) )
#define getbit(x,y)  ( a[x][y >> 3] &   (1 << (y & 7)) )

int n, s, x, lev;
int a[N][N/8], d[32010];

void read ()
{
   int i, j, v, x = 0;

   //freopen( "1176.in", "rt", stdin );
   scanf( "%d%d", &n, &s );
   for ( i = 1; i <= n; i++ )
       for ( j = 1; j <= n; j++ )
       {
          scanf( "%d", &v );
          if ( !v && i != j )
             setbit1( i, j ), x++;
       }
   if ( !x ) exit( 0 );
}

void ciclu (int s)
{
   int j;

   lev++;

   for ( j = 1; j <= n; j++ )
       if ( getbit( s, j ) )
       {
          setbit0( s, j );
          ciclu( j );
       }

   d[++d[0]] = s;
/*   if ( !x || lev == 1 )
      printf( "%d ", s );
   else
      printf( "%d\n%d ", s, s );
   x = s;

   lev--;*/
}

int main ()
{
   int i;

   read();

   ciclu( s );
   for ( i = 1; i < d[0]; i++ )
       printf( "%d %d\n", d[i], d[i + 1] );

   return 0;
}

#include<iostream.h>
int*conn[1001];
int*done[1001];
int quan[1001];
void razrul(int);
int *tstr;
void main(){
    int str[1001];
    tstr=new int[32200];
    int i,j,n,q,a;
    cin >> n >> a;
    a--;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            cin >> str[j];
        q=0;
        str[i]=1;
        for(j=0;j<n;j++)
            if(str[j]==0)
                q++;
        if(q!=0)
        {
            conn[i]=new int[q];
            done[i]=new int[q];
        }
        quan[i]=0;
        for(j=0;j<n;j++)
            if(str[j]==0)
            {
                conn[i][quan[i]]=j;
                done[i][quan[i]]=0;
                quan[i]++;
            }
    }
    razrul(a);
}
void razrul(int a){
    tstr[0]=a;
    int *tstr1;
    int ptstr=1,a0=a,i;
    while(1)
    {
        for(i=0;i<quan[a];i++)
            if(done[a][i]==0)
            {
                done[a][i]=1;
                a=conn[a][i];
                tstr[ptstr]=a;
                ptstr++;
                break;
            }
        if(a==a0)
            break;
    }
    if(ptstr!=1)
        tstr1=new int[ptstr];
    else
        return ;
    for(i=0;i<ptstr;i++)
        tstr1[i]=tstr[i];
    for(i=0;i<ptstr-1;i++)
    {
        cout <<tstr1[i]+1<<" "<<tstr1[i+1]+1<<"\n";
        razrul(tstr1[i+1]);
    }
}