fork download 
  1.  
  2.  
  3. #include<stdio.h>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<deque>
  7. #include<vector>
  8. using namespace std;
  9. int main()
  10. {
  11.     int n1,n2,d;
  12.     scanf("%d%d%d",&n1,&n2,&d);
  13.     while(n1!=0&n2!=0&&d!=0)
  14.     {
  15.          	int* count2=(int*)calloc(sizeof(int),n1+n2+4);
  16.         	deque<pair<int,int> > q;
  17.                vector<int> v[n1+n2+1];
  18.     	int i;
  19.     	for(i=0;i<d;i++)
  20.     	{
  21.     		int ele1,ele2;
  22.     		scanf("%d%d",&ele1,&ele2);
  23.     		v[ele2].push_back(ele1);
  24.     		count2[ele1]++;
  25.     	}
  26.     	int count[n1+n2+2];
  27.     	int i3;
  28.     	int ans[2];
  29.     	for(i3=0;i3<2;i3++)
  30.     	{
  31.     	for(i=1;i<=n1+n2;i++)
  32.     	  count[i]=count2[i];
  33.     	for(i=1;i<=n1+n2;i++)
  34.     	{
  35.     		if(count[i]!=0)
  36.     			continue;
  37.     		if(i<=n1)
  38.     			q.push_back(make_pair (1,i));
  39.     		else
  40.     		{
  41.                 if(i3==0)
  42.     			q.push_back(make_pair(2,i));
  43.     			else
  44.     			q.push_front(make_pair(2,i));
  45.             }
  46.     	}
  47.     	int count1=2;
  48.     	while(!q.empty())
  49.     	{
  50.     		pair<int,int> p=q.front();
  51.     		q.pop_front();
  52.     		if(!q.empty()&&q.front().first!=p.first)
  53.     			count1+=1;
  54.     		int n=v[p.second].size();
  55.     		int i;
  56.     		for(i=0;i<n;i++)
  57.     		{
  58.     			count[v[p.second][i]]--;
  59.     			if(count[v[p.second][i]]==0)
  60.     			{
  61.     				pair<int,int> p1;
  62.     				p1.second=v[p.second][i];
  63.     				if(v[p.second][i]<=n1)
  64.     					p1.first=1;
  65.     				else
  66.     					p1.first=2;
  67.     				if(p1.first==p.first)
  68.     					q.push_front(p1);//,(printf("inserting front %d %d\n",p1.first,p1.second));
  69.     				else
  70.     					q.push_back(p1);//,printf("inserting back %d %d\n",p1.first,p1.second);
  71.     			}
  72.     		}
  73.  
  74.     	}
  75.     	ans[i3]=count1;
  76.  
  77.      }
  78.     	printf("%d\n",min(ans[0],ans[1]));
  79.     	scanf("%d%d%d",&n1,&n2,&d);
  80.  
  81.     }
  82. 	return 0;
  83. }
Success #stdin #stdout 0s 2868KB
comments (?)
stdin 
3 2 2
1 4
2 4
0 0 0
stdout 
3
https://ideone.com/Q7nCGa
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!