1229 - Sub-dictionary

[@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?

[red_apricot]

What is the output for this:

Code: Select all

7
a b f 
b a
f e
e f
g a f
d e
c f

My out put is

Code: Select all

4 a b e f

So, my algo is to obtain the DAG and report all the SCCs with cardinality >= 2 or with indegree 0. Still WA.

[brianfry713]

For input:

Code: Select all

7
a b f 
b a
f e
e f
g a f
d e
c f
0

AC output:

Code: Select all

4
a b e f

[red_apricot]

Ah, what about these random-generated ones:

Code: Select all

13
yzkg vcjqig 
wsd w lzjshhp omol 
w wsd urhfyb atde lzjshhp unqqc urhfyb 
urhfyb wsd vcjqig nupe nupe 
lzjshhp wsd gkh ygjd wsd ygjd 
atde qyy vcjqig omol urhfyb ygjd 
nupe wsd atde 
vcjqig unqqc unqqc qyy wsd urhfyb yzkg 
ygjd lzjshhp omol atde lzjshhp wsd nupe 
qyy wsd omol atde w 
gkh nupe unqqc urhfyb vcjqig lzjshhp atde 
unqqc ygjd lzjshhp 
omol vcjqig 
11
euzrg ilnt q lfmlpj 
vcs lfmlpj 
aielg xacto t 
q vzkpwai ilnt 
vzkpwai ldgny 
xacto vzkpwai 
zxfh q euzrg t 
ilnt xacto 
lfmlpj q vzkpwai 
ldgny zxfh lfmlpj aielg 
t euzrg xacto euzrg zxfh 
6
gaxw cm kx ovxnwit 
ovxnwit gaxw gaxw 
zfpvtiy gaxw bch 
cm kx zfpvtiy zfpvtiy 
bch gaxw gaxw 
kx ovxnwit bch gaxw 
3
h vl 
vl jdqig 
jdqig vl 
5
apa tvrrct 
fir lyaj eaxpf 
tvrrct apa eaxpf 
lyaj tvrrct 
eaxpf apa 
16
zerjobh inwppwu njbc 
xamjdn idzmr sxdc xxh 
njbc pe xxh pe 
idzmr hb ya zerjobh xamjdn ij xxh sobk g 
kwoewkd hb gpp 
sxdc g pe inwppwu njbc xxh 
gpp inwppwu 
ya xamjdn zerjobh ij idzmr inwppwu gpp gpp 
pe g sobk kwoewkd ya idzmr xamjdn sobk g 
hb xamjdn g kwoewkd sxdc xamjdn 
inwppwu gpp kwoewkd pe idzmr ij xamjdn g 
z sxdc sxdc g ij xamjdn 
sobk zerjobh inwppwu ij zerjobh idzmr 
g njbc kwoewkd ya njbc ya sobk sxdc inwppwu 
xxh kwoewkd gpp g z gpp 
ij xamjdn gpp inwppwu inwppwu inwppwu 
21
ydenvz q dwvfcfk q ajisxdk gpi dwvfcfk gecbyf zrml 
zrml ggvz khdjq n 
ajisxdk zrml ufwczaf n ukdrcnj dwvfcfk mwe ufwczaf rlgmvfx sayif 
ukdrcnj g 
ggvz mbapnqs gpi mwe rlgmvfx 
p n ajisxdk khdjq snv mwe zrml mbapnqs 
khdjq sqrkihw snv sayif gpi ajisxdk q mwe gecbyf dwvfcfk 
gpi mbapnqs dwvfcfk b dwvfcfk rlgmvfx 
b rlgmvfx g rlgmvfx ydenvz sqrkihw 
gecbyf n p g ufwczaf ggvz sqrkihw ydenvz snv ajisxdk 
sayif ajisxdk gpi gecb[code]

yf n gpi mwe ufwczaf rlgmvfx ydenvz mwe
q snv khdjq ukdrcnj b ydenvz g
mwe dwvfcfk dwvfcfk sayif ggvz ufwczaf gpi
mbapnqs ydenvz
dwvfcfk rlgmvfx n zrml rlgmvfx
g gpi
rlgmvfx g p sayif ydenvz g zrml
ufwczaf sqrkihw sayif p gpi mbapnqs p
sqrkihw gpi b sayif gpi n mwe ajisxdk mbapnqs
snv n g ggvz mbapnqs rlgmvfx sayif zrml q
n snv p sayif mbapnqs ukdrcnj sayif ufwczaf sayif sayif mwe
0[/code]

My output is:

Code: Select all

13
atde gkh lzjshhp nupe omol qyy unqqc urhfyb vcjqig w wsd ygjd yzkg
10
aielg euzrg ilnt ldgny lfmlpj q t vzkpwai xacto zxfh
6
bch cm gaxw kx ovxnwit zfpvtiy
2
jdqig vl
3
apa eaxpf tvrrct
16
g gpp hb idzmr ij inwppwu kwoewkd njbc pe sobk sxdc xamjdn xxh ya z zerjobh
21
ajisxdk b dwvfcfk g gecbyf ggvz gpi khdjq mbapnqs mwe n p q rlgmvfx sayif snv sqrkihw ufwczaf ukdrcnj ydenvz zrml

Thanks.

[red_apricot]

...and also this huge one:

Code: Select all

100
ubghztqgvtenc prxdpnwyaamtb 
btxbiiajcsjlp goqotulirejot lteqzvhspkijh 
oactcxkkhzknr mlfjeeclhjghq 
qmgveexsmxljo cqdlmpkzqopcg bgpckbjshokeg fwsugvvnmizit pzltzvinsbvsf 
cxbtstcuiqvqo nyhfqbpvuwmwj vdmulrwscqhau acdvznnlaynbz tcgdnnvqgkfgh 
pchvcgicjqibi hznfhjrruazow albgzwdhytdqq 
zqtrwwrhxtend vdmulrwscqhau qmgveexsmxljo pznqhvyssmriv uxbymubhllxgg 
pgymtffwmzodc pznqhvyssmriv cxbtstcuiqvqo xqnxcbvccjeeo 
qeyjqryrpjydh xwcjtptzjmvcl 
zbegdwrgnswqj zapaymhftdwkc qfpcuypankzbv debxlysqpelsl 
wguoztswjobgy qeyjqryrpjydh 
tiafbvyamsrlx tcgdnnvqgkfgh gqlvyuyutqlto albgzwdhytdqq 
ajfbmitlingmm umheuosxrdkdt pznqhvyssmriv azmquwwimmezt wguoztswjobgy 
lgxcwllcjmsmz albgzwdhytdqq nyhfqbpvuwmwj 
mlbeuthxurwlg asbockbpozgch lhelcmixssdfi 
nbydwtaqkojua kwxxnzbauaqqp 
crnjyyqytmqwa inwuuzfdizily benbwvwklbewe 
gqlvyuyutqlto rzofjdouzegmo xqnxcbvccjeeo 
qcvatiubegura thgqrjqshfgoj xwcjtptzjmvcl xuxnukzvmtfkv 
txfvscvgmhppl gppqlxapdekkr 
kwxxnzbauaqqp ebyrzvogiuguw 
ulgomyurpfpqe ecopphcjubpxu crnjyyqytmqwa thgqrjqshfgoj ebyrzvogiuguw 
mlfjeeclhjghq ogtizuwzpfapd uxbymubhllxgg nizrljlengcvs ybadtcarvceaa 
pkjjuhofzkmcg ubghztqgvtenc eiyxcaopyzllp 
tflrnitabzfnz cbilbbdzadhaa zbooocfpqdckx orvovgypyhuyu 
vhagonhgehbph ogtizuwzpfapd 
uwvcsxqdboyuh lgxcwllcjmsmz cxbtstcuiqvqo pgymtffwmzodc 
iixkovsruazed qeyjqryrpjydh 
umheuosxrdkdt inwuuzfdizily aasfivpcwyipd mlfjeeclhjghq inwuuzfdizily 
ztnuechsheqku yjnfphzsowtht pgymtffwmzodc 
nyifpkxldrurc gppqlxapdekkr vtazguibbzhvb ogtizuwzpfapd uxbymubhllxgg 
edbexrfgreelz sauwuiraoffhw entehhsqmaxpb bgpckbjshokeg uwvcsxqdboyuh 
xuxnukzvmtfkv uwvcsxqdboyuh cbilbbdzadhaa nvnaiyfujtdeu 
vdmulrwscqhau tcgdnnvqgkfgh mlfjeeclhjghq 
imjnevtmmbkgj mlfjeeclhjghq btxbiiajcsjlp ajfbmitlingmm 
fwsugvvnmizit goqotulirejot uwvcsxqdboyuh ecopphcjubpxu hznfhjrruazow 
ecopphcjubpxu edbexrfgreelz mlbeuthxurwlg 
cbilbbdzadhaa lgxcwllcjmsmz ogtizuwzpfapd tflrnitabzfnz nvnaiyfujtdeu 
nyhfqbpvuwmwj nyifpkxldrurc goqotulirejot cbilbbdzadhaa benbwvwklbewe 
benbwvwklbewe nbydwtaqkojua rzofjdouzegmo mlfjeeclhjghq 
nvnaiyfujtdeu mlbeuthxurwlg xwcjtptzjmvcl oactcxkkhzknr 
vlulvfhpmgptc thgqrjqshfgoj goqotulirejot iixkovsruazed 
debxlysqpelsl vlulvfhpmgptc rzofjdouzegmo zapaymhftdwkc 
ybadtcarvceaa jukvzvgnmtuml crnjyyqytmqwa 
ogtizuwzpfapd vdmulrwscqhau pgymtffwmzodc 
gncrfpuzojnww ecopphcjubpxu xqnxcbvccjeeo 
ocdgcshulfxln edbexrfgreelz vtazguibbzhvb vlulvfhpmgptc 
ebyrzvogiuguw vdmulrwscqhau 
eiyxcaopyzllp jukvzvgnmtuml wguoztswjobgy bgpckbjshokeg 
xqnxcbvccjeeo nyifpkxldrurc 
azmquwwimmezt pgymtffwmzodc pchvcgicjqibi 
zapaymhftdwkc debxlysqpelsl 
inwuuzfdizily uxbymubhllxgg cbilbbdzadhaa vlulvfhpmgptc 
rdxlergeasqdq btxbiiajcsjlp nyifpkxldrurc 
gppqlxapdekkr nizrljlengcvs qmgveexsmxljo tflrnitabzfnz 
xcpgrqjklazbj cbjomnzyhzvgc 
pzltzvinsbvsf vdmulrwscqhau prxdpnwyaamtb vhagonhgehbph prmawlqznszgn 
tcgdnnvqgkfgh prmawlqznszgn 
bgpckbjshokeg ubghztqgvtenc thgqrjqshfgoj 
acdvznnlaynbz nyhfqbpvuwmwj 
oewnxntfmkuto cbjomnzyhzvgc nizrljlengcvs 
pfeziugdkrpaj qmgveexsmxljo qmgveexsmxljo xqnxcbvccjeeo 
goqotulirejot albgzwdhytdqq ubghztqgvtenc btxbiiajcsjlp 
prmawlqznszgn mlbeuthxurwlg 
jukvzvgnmtuml thgqrjqshfgoj pznqhvyssmriv 
kvdwmyjceqjen vhagonhgehbph 
pgsmruldpissz lhelcmixssdfi rdxlergeasqdq mlbeuthxurwlg 
zmhxajwjeoavn qqxizcqsqcadw umheuosxrdkdt ubghztqgvtenc imjnevtmmbkgj 
kdbuetpgiadrj lhelcmixssdfi txfvscvgmhppl 
pznqhvyssmriv kdbuetpgiadrj inwuuzfdizily kleqqltrhhmib 
entehhsqmaxpb iixkovsruazed 
rzofjdouzegmo zbooocfpqdckx 
lteqzvhspkijh pzltzvinsbvsf kwxxnzbauaqqp pchvcgicjqibi acdvznnlaynbz 
orvovgypyhuyu rdxlergeasqdq qqxizcqsqcadw ubghztqgvtenc vhagonhgehbph 
prxdpnwyaamtb aasfivpcwyipd 
asbockbpozgch goqotulirejot edbexrfgreelz cqdlmpkzqopcg 
zbooocfpqdckx debxlysqpelsl 
aasfivpcwyipd uwvcsxqdboyuh ubghztqgvtenc qcvatiubegura kleqqltrhhmib 
uxbymubhllxgg iqapxifxgtxgc 
yjnfphzsowtht aosaqoktravpb vtazguibbzhvb xhfnttjdlamxb 
aosaqoktravpb tcgdnnvqgkfgh zqtrwwrhxtend pznqhvyssmriv 
tstujakgxsimh debxlysqpelsl ogtizuwzpfapd xuxnukzvmtfkv 
cqdlmpkzqopcg benbwvwklbewe mlbeuthxurwlg lteqzvhspkijh orvovgypyhuyu 
cbjomnzyhzvgc lteqzvhspkijh uwvcsxqdboyuh cqdlmpkzqopcg 
dzazbgmmpfvlg gppqlxapdekkr qeyjqryrpjydh rdxlergeasqdq hznfhjrruazow 
qfpcuypankzbv nyifpkxldrurc tiafbvyamsrlx 
kleqqltrhhmib ulgomyurpfpqe oewnxntfmkuto 
tasifzrfubsgc nbydwtaqkojua kdbuetpgiadrj 
nizrljlengcvs imjnevtmmbkgj ajfbmitlingmm pznqhvyssmriv nbydwtaqkojua 
zjeudvttofebs qeyjqryrpjydh qeyjqryrpjydh ebyrzvogiuguw 
qqxizcqsqcadw eiyxcaopyzllp zmhxajwjeoavn pznqhvyssmriv 
xhfnttjdlamxb qcvatiubegura 
hznfhjrruazow zbooocfpqdckx aasfivpcwyipd 
lhelcmixssdfi oewnxntfmkuto oactcxkkhzknr 
sauwuiraoffhw gppqlxapdekkr lteqzvhspkijh azmquwwimmezt kleqqltrhhmib 
xwcjtptzjmvcl pchvcgicjqibi oewnxntfmkuto 
vtazguibbzhvb vdmulrwscqhau prxdpnwyaamtb 
thgqrjqshfgoj gqlvyuyutqlto 
iqapxifxgtxgc asbockbpozgch 
albgzwdhytdqq bgpckbjshokeg xcpgrqjklazbj qmgveexsmxljo nbydwtaqkojua 
0

[/size]

My output is

Code: Select all

82
aasfivpcwyipd acdvznnlaynbz ajfbmitlingmm albgzwdhytdqq asbockbpozgch azmquwwimmezt benbwvwklbewe bgpckbjshokeg btxbiiajcsjlp cbilbbdzadhaa cbjomnzyhzvgc cqdlmpkzqopcg crnjyyqytmqwa cxbtstcuiqvqo debxlysqpelsl ebyrzvogiuguw ecopphcjubpxu edbexrfgreelz eiyxcaopyzllp entehhsqmaxpb fwsugvvnmizit goqotulirejot gppqlxapdekkr gqlvyuyutqlto hznfhjrruazow iixkovsruazed imjnevtmmbkgj inwuuzfdizily iqapxifxgtxgc jukvzvgnmtuml kdbuetpgiadrj kleqqltrhhmib kwxxnzbauaqqp lgxcwllcjmsmz lhelcmixssdfi lteqzvhspkijh mlbeuthxurwlg mlfjeeclhjghq nbydwtaqkojua nizrljlengcvs nvnaiyfujtdeu nyhfqbpvuwmwj nyifpkxldrurc oactcxkkhzknr oewnxntfmkuto ogtizuwzpfapd orvovgypyhuyu pchvcgicjqibi pgymtffwmzodc prmawlqznszgn prxdpnwyaamtb pzltzvinsbvsf pznqhvyssmriv qcvatiubegura qeyjqryrpjydh qmgveexsmxljo qqxizcqsqcadw rdxlergeasqdq rzofjdouzegmo sauwuiraoffhw tcgdnnvqgkfgh tflrnitabzfnz thgqrjqshfgoj txfvscvgmhppl ubghztqgvtenc ulgomyurpfpqe umheuosxrdkdt uwvcsxqdboyuh uxbymubhllxgg vdmulrwscqhau vhagonhgehbph vlulvfhpmgptc vtazguibbzhvb wguoztswjobgy xcpgrqjklazbj xqnxcbvccjeeo xuxnukzvmtfkv xwcjtptzjmvcl ybadtcarvceaa zapaymhftdwkc zbooocfpqdckx zmhxajwjeoavn

[/size]

And also, can there be input like this:

Code: Select all

2
a
b

In this case, do we report zero or one?

EDIT: No, there are no words with empty definition, checked it with assert().