You are not logged in. Please login at www.codechef.com to post your questions!

×

HELP..sereja and graph(seagrp)

basically the code searches for a path in the graph using dfs..that there is no node repeated in the path.. (for ex. 1->2->3->4->5)for 5 nodes..and runs for all 5 nodes..if there is a path with no node repeated than it prints yes else prints no .........i don't know why u am getting wrong answer

#include<stdio.h>
int a[101][101],reach[101],n,visit[101];

void dfs(int v)
{

                             int i;

                             reach[v]=1;

                             for(i=1;i<=n;i++)
                                 if(a[v][i] && !reach[i])
                                  {
                                      visit[v]++;
                                       dfs(i);
                                  }
                   }
int main()

{

    int i,j,count=0,m,t,x,y,count2;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            reach[i]=0;
            for(j=1;j<=n;j++)
                a[i][j]=0;
            visit[i]=0;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            if(x!=y)
                        {
                            a[x][y]=1;
                            a[y][x]=1;
                        }
        }
        for(i=1;i<=n;i++)
        {
            count=0;count2=0;
            for(j=1;j<=n;j++)
            {
                visit[j]=0;
                reach[j]=0;
            }
            dfs(i);
            for(j=1;j<=n;j++)
            {
                if(reach[j])
                    count++;
                if(visit[j]==1)
                    count2++;
            }
            if(count==n&&count2==n-1&&m>=n&&n>1)
                break;
        }
        if(i==n+1)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}
This question is marked "community wiki".

asked 28 Oct '14, 18:44

ankit10000's gravatar image

2★ankit10000
12
accept rate: 0%

edited 28 Oct '14, 21:07

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,657
×86
×53
×51

question asked: 28 Oct '14, 18:44

question was seen: 839 times

last updated: 28 Oct '14, 21:07