Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * =====================================================================================
- *
- * Filename: 1669.cpp
- *
- * Description:
- *
- * Version: 1.0
- * Created: 13-11-2015 14:32:49
- * Revision: none
- * Compiler: gcc
- *
- * Author:
- * Company:
- *
- * =====================================================================================
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <algorithm>
- #include <vector>
- #include <string.h>
- #include <math.h>
- #include <set>
- #include <iostream>
- #include <queue>
- #include <string>
- #include <ctype.h>
- #include <stack>
- //#include<time.h>
- //#include<unordered_map>
- #include <map>
- //#include <windows.h>
- using namespace std;
- template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
- typedef long long int llint;
- typedef unsigned long long int ullint;
- #define FOR(i,a,b) for(int i = a;i<b;++i)
- #define EPS 1e-3
- #define INF 100002
- int deps[INF];
- vector<vector<int> > depsDeste(INF);
- inline int solve(int cd, int n1, int n2){
- queue<int> pacotes[2];
- //vector<vector<int> > depsDesteAux = depsDeste;
- int depsAux[n1+n2];
- int ans = 0;
- FOR(i,0,n1+n2) depsAux[i] = deps[i];
- FOR(i,0,n1)
- if(!deps[i]) pacotes[0].push(i);
- FOR(i,n1,n1+n2)
- if(!deps[i]) pacotes[1].push(i);
- //cout<<pacotes[0].size()<< " " << pacotes[0].front()<<endl;
- //cout<<pacotes[1].size()<< " " << pacotes[1].front()<<endl;
- while(!pacotes[0].empty() || !pacotes[1].empty()){
- while(!pacotes[cd].empty()){
- int topo = pacotes[cd].front();
- pacotes[cd].pop();
- FOR(i,0,(int)depsDeste[topo].size()){
- int aux = --depsAux[depsDeste[topo][i]];
- //cout<<"cd: " << cd << " here:"<<depsDeste[topo][i]<< " de quem: "<< topo << " aux: "<<aux<<endl;
- if(!aux)
- if(depsDeste[topo][i]>=n1) pacotes[1].push(depsDeste[topo][i]);
- else pacotes[0].push(depsDeste[topo][i]);
- }
- }
- //cout<<"Simulando "<<cd<<" ans:" <<ans<<endl;
- if(cd) cd = 0;
- else cd = 1;
- ans++;
- }
- return ans+1;
- }
- int main(){
- ios::sync_with_stdio(false);
- int n1,n2,d;
- while(cin>>n1>>n2>>d){
- if(!n1 && !n2) break;
- memset(deps,0,sizeof deps);
- FOR(i,0,n1+n2+1) depsDeste[i].clear();
- FOR(i,0,d){
- int a,b;
- cin>>a>>b;
- a--, b--;
- deps[a]++;
- depsDeste[b].push_back(a);
- }
- cout << min(solve(0,n1,n2), solve(1,n1,n2)) <<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement