things that i have done
1.install all the packages from the first disc if a package from the disc which we have inserted becomes independent i will queue it up front
if a package from another disc becomes independent i will queue it in the back
2.install all the packages from the second disc if a package from the disc which we have inserted becomes independent i will queue it up front
if a package from another disc becomes independent i will queue it in the back
i.e: initially we have two possibities either start from second or first disc and then proceed as such..
i have taken the minimum out of them
with proper indentation
ideone.com/Q7nCGa
[code]
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int main()
{
int n1,n2,d;
scanf("%d%d%d",&n1,&n2,&d);
while(n1+n2+d)
{
int* count2=(int*)calloc(sizeof(int),n1+n2+4);
deque<pair<int,int> > q;
vector<int> v[n1+n2+1];
int i;
for(i=0;i<d;i++)
{
int ele1,ele2;
scanf("%d%d",&ele1,&ele2);
v[ele2].push_back(ele1);
count2[ele1]++;
}
int count[n1+n2+2];
int i3;
int ans[2];
for(i3=0;i3<2;i3++)
{
for(i=1;i<=n1+n2;i++)
count[i]=count2[i];
for(i=1;i<=n1+n2;i++)
{
if(count[i]!=0)
continue;
if(i<=n1)
q.push_back(make_pair (1,i));
else
{
if(i3==0)
q.push_back(make_pair(2,i));
else
q.push_front(make_pair(2,i));
}
}
int count1=2;
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop_front();
if(!q.empty()&&q.front().first!=p.first)
count1+=1;
int n=v[p.second].size();
int i;
for(i=0;i<n;i++)
{
count[v[p.second][i]]--;
if(count[v[p.second][i]]==0)
{
pair<int,int> p1;
p1.second=v[p.second][i];
if(v[p.second][i]<=n1)
p1.first=1;
else
p1.first=2;
if(p1.first==p.first)
q.push_front(p1);//,(printf("inserting front %d %d\n",p1.first,p1.second));
else
q.push_back(p1);//,printf("inserting back %d %d\n",p1.first,p1.second);
}
}
}
ans[i3]=count1;
}
printf("%d\n",min(ans[0],ans[1]));
scanf("%d%d%d",&n1,&n2,&d);
}
return 0;
}
[/code]
