1229 - Sub-dictionary (Why WA)

[@li_kuet]

first i did top sort using dfs
then find the scc
then again did dfs in the top list order and calculate them .

i dont know what is wrong
is it the wrong algorithm or system i applied ???

please help

[brianfry713]

Doesn't match the sample I/O.

[@li_kuet]

How can i solve this problem ??? @brianfry713

[brianfry713]

DFS

[plamplam]

I'm getting wrong answer, what is the output for the test case? The problem is ambigous...it doesn't clearly state what should be the output when multiple solutions exists.

Code: Select all

9
d e
e f
f d
a b
b c
c a
g h
h i
i g
0

[brianfry713]

AC output for your input:

Code: Select all

9
a b c d e f g h i

[Mukit Chowdhury]

what should be the output for input...

5
a s d f
b d f r
c q w e
f s
g h
0

My code gives...

3
d f s

It's wrong...isn't it ??
I am trying using topological sort ... Can't it be done using topological sort ???

[brianfry713]

Your input isn't valid.
A dictionary must contain the definition for any word that appears in the explanation of another word.

[Mukit Chowdhury]

Checking...

[Ronok1307]

WA.
My algo -
1.use tarjan to find the scc dag
2. build dag graph
3. visit the nodes in the dag in topological order and visit the connected nodes
4. all the nodes in the dag, that act as a starting point for the dfs() call are the answers.
5. list all the nodes of the answers, sort them and show output

is the algo wrong?

Code: Select all

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <sstream>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;


struct node
{
   int id,low;
   bool operator <(const node &a)const
   {
      return a.low>low;
   }
}asd;

priority_queue <node> pq;
char ss[100];
string s,p,arr[105];
map <string,int> mp;
bool v[105],vv[105],vvv[105];
int adj[105][105],pre[105],post[105],ma,ll,l,dagl,whichdag[105],dagpre[105],dagpost[105],dagadj[105][105],lll;
vector <int> dag[105];
vector <string> ans;
stack <int> x;

void clear()
{
   while(!pq.empty())
      pq.pop();
   mp.clear();
   memset(v,0,sizeof(v));
   memset(vv,0,sizeof(vv));
   memset(vvv,0,sizeof(vvv));
   memset(adj,0,sizeof(adj));
   memset(dagadj,0,sizeof(adj));
   for(int i=0;i<dagl;i++)
      dag[i].clear();
   ans.clear();
   while(!x.empty())
      x.pop();
}

void rec(int n)
{
   pre[n]=post[n]=ll++;
   v[n]=vv[n]=1;
   x.push(n);
   int a,i;
   for(i=0;i<l;i++)
   {
      if(adj[i][n])
      {
         if(!v[i])
            rec(i);
         if(vv[i])
            post[n]=post[n]<post[i]?post[n]:post[i];
      }
   }
   if(pre[n]==post[n])
   {
      while(1)
      {
         a=x.top();
         x.pop();
         vv[a]=0;
         dag[dagl].push_back(a);
         whichdag[a]=dagl;
         if(a==n)
            break;
      }
      dagl++;
   }
}

void dfs(int n,int s)
{
   dagpre[n]=lll++;
   v[n]=1;
   int i;
   for(i=0;i<dagl;i++)
   {
      if(dagadj[n][i] && !v[i])
         dfs(i,s);
   }
   dagpost[n]=lll++;
   if(s)
   {
      asd.id=n;
      asd.low=dagpost[n];
      pq.push(asd);
   }
}

int main()
{
   //freopen("in.txt","r",stdin);
   int a,b,c,i,j,k,n,t;
   while(1)
   {
      sscanf(gets(ss),"%d",&n);
      if(!n)
         break;
      l=0;
      while(n--)
      {
         getline(cin,s);
         stringstream line(s);
         line>>p;
         if(mp.find(p)==mp.end())
         {
            mp[p]=l;
            b=l;
            arr[l]=p;
            l++;
         }
         else
            b=mp[p];
         while(line>>p)
         {   
            if(mp.find(p)==mp.end())
            {
               mp[p]=l;
               a=l;
               arr[l]=p;
               l++;
            }
            else
               a=mp[p];
            adj[a][b]=1;
         }
      }
      dagl=ll=0;
      for(i=0;i<l;i++)
      {
         if(!v[i])
            rec(i);
      }
      memset(v,0,sizeof(v));
      for(i=0;i<dagl;i++)
      {
         for(j=0;j<dag[i].size();j++)
         {
            a=dag[i][j];
            for(k=0;k<l;k++)
            {
               if(adj[a][k] && whichdag[k]!=i)
                  dagadj[i][whichdag[k]]=1;
            }
         }
      }
      lll=0;
      for(i=0;i<dagl;i++)
      {
         if(!v[i])
            dfs(i,1);
      }
      memset(v,0,sizeof(v));
      while(!pq.empty())
      {
         asd=pq.top();
         pq.pop();
         a=asd.id;
         if(!v[a])
         {   dfs(a,0);
            for(i=0;i<dag[a].size();i++)
               ans.push_back(arr[dag[a][i]]);
         }
      }
      sort(ans.begin(),ans.end());
      printf("%d\n",ans.size());
      for(i=0;i<ans.size();i++)
      {
         if(i)
            printf(" ");
         cout<<ans[i];
      }
      printf("\n");
      clear();
   }
   return 0;
}

[mostafiz93]

There is one space character(' ') at the last of each input line in the sample input.
Should we consider this for every input?

Can anyone clarify this issue?