then find the scc
then again did dfs in the top list order and calculate them .
i dont know what is wrong
![:(](./images/smilies/icon_frown.gif)
is it the wrong algorithm or system i applied ???
please help
![:(](./images/smilies/icon_frown.gif)
Moderator: Board moderators
Code: Select all
9
d e
e f
f d
a b
b c
c a
g h
h i
i g
0
Code: Select all
9
a b c d e f g h i
My code gives...5
a s d f
b d f r
c q w e
f s
g h
0
It's wrong...isn't it ??3
d f s
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;
}
Code: Select all
7
a b f
b a
f e
e f
g a f
d e
c f
Code: Select all
4 a b e f
Code: Select all
7
a b f
b a
f e
e f
g a f
d e
c f
0
Code: Select all
4
a b e f
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]
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
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
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
Code: Select all
2
a
b