Code: Select all
Input:
3
a
b
c
4
a b
b c
a b
b c
output:
Case #1: Dilbert should drink beverages in this order: a b c.
Moderator: Board moderators
Code: Select all
Input:
3
a
b
c
4
a b
b c
a b
b c
output:
Case #1: Dilbert should drink beverages in this order: a b c.
Code: Select all
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
int s[200];
int main()
{
int n,er=1,k,i,j,cnt,fr;
while(scanf("%d",&n)!=EOF)
{int mat[n+1][n+1],deg[n+1],degin[n+1],minc[n+1][n+1],l[n+1],g[n+1],mark[n+1],ans[n+1];
map<string,int> m;
map<int,string> d;
char c[52],st[52];
for(i=0;i<=n;i++)
{
deg[i]=degin[i]=g[i]=ans[i]=mark[i]=l[i]=0;
}
for(i=1;i<=n;i++)
{
cin>>c;
m[c]=i;
d[i]=c;
}
int me,q;cin>>me;
for(i=1;i<=me;i++)
{
cin>>c>>st;
for(j=0;j<=deg[m[c]];j++)
{q=0;
if(mat[m[c]][j]==m[st]) {q=1;break;}
}
if(q==0)
{mat[m[c]][deg[m[c]]++]=m[st];
minc[m[st]][degin[m[st]]++]=m[c];
g[m[st]]=1;
}
}k=0;
for(i=1;i<=n;i++)
{
if(g[i]==0) {l[k]=i;k++;}
}
sort(l,l+k);int rear=k-1,front=0;
for(i=0;i<k;i++)
{
s[i]=l[i];
l[i]=0;
}
k=0;
while(front<=rear)
{
fr=s[front];
mark[fr]=1;
ans[k]=fr;k++;
front++;
for(i=0;i<deg[fr];i++)
{
cnt=0;
if(mark[mat[fr][i]]==0)
{for(j=0;j<degin[mat[fr][i]];j++)
{
if(mark[minc[mat[fr][i]][j]]==0)
{
cnt++;
}
}
if(cnt==0)
{
s[++rear]=mat[fr][i];
//mark[mat[fr][i]]=1;
}
}
}
sort(s+front,s+rear+1);
}
cout<<"Case #"<<er<<": Dilbert should drink beverages in this order: ";
for(i=0;i<k-1;i++)
{
cout<<d[ans[i]]<<" ";
}cout<<d[ans[k-1]];cout<<".\n\n";er++;
}
return 0;
}
Code: Select all
#include<iostream>
#include<list>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
list<int>*adj;
string S[101];
void topologicalUtil(int k,bool visited[],stack<int>&stk)
{
visited[k]=true;
list<int>::iterator i;
for (i=adj[k].begin(); i!=adj[k].end(); ++i)
if (!visited[*i])
topologicalUtil(*i, visited, stk);
stk.push(k);
}
void topologicalSort()
{
stack<int>stk;
bool *visited=new bool[n];
for(int i=0;i<n;i++) visited[i]=false;
for(int i=0;i<n;i++)
{
if(!visited[i])
{
topologicalUtil(i,visited,stk);
}
}
while(stk.empty()==false)
{
int i;
i=stk.top();
cout<<S[i]<<" ";
stk.pop();
}
printf("\n");
}
int findIndex(string a)
{
for(int i=0;i<n;i++)
if(S[i]==a) return i;
return -1;
}
int main()
{
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
string a,b;
int x,y,cs=1;
while (scanf("%d",&n)!=EOF)
{
adj=new list<int>[n];
for(int i=0;i<n;i++)
{
cin>>a;
S[i]=a;
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>a>>b;
x=findIndex(a);
y=findIndex(b);
adj[x].push_back(y);
}
cout<<"Case #"<<cs<<": Dilbert should drink beverages in this order: ";
topologicalSort();
printf("\n");
cs++;
}
return 0;
}
:(
I think you misunderstood the problem.In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input.
The problem statement is not clear.Martin Macko wrote:I guess the problemsetter meant to write that beverage A should be brunk before beverage B if A has less alcohol content than B or beverages A and B are independent and beverage A is earlier in the input, where two beverages A and B are independent if and only if there is no (even indirect) alcoholic relation between them in the input and there is no yet undrunk beverage C with less alcohol content than A or B.little joey wrote:Yes, good analysis. I was so fed up with this problem, I didn't bother to look anymore after I got AC in my third attempt (although I knew my program wouldn't cover all possible cases). I guess the program should print "impossible" or "illegal" in such cases.
I think the outputs for examples mentioned in the problem statement correspond to this definition. Also my AC assumed that.