Submission #666609

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int n;
map<int,set<int> > in;
bool visited[100];
void dfs(int cur){
	if(!in[cur].empty())	return;
	visited[cur]=true;
	for(int i=0;i<n;i++){
		in[i].erase(cur);
	}
	for(int i=0;i<n;i++){
		if(!visited[i]&&in[i].empty())	dfs(i);
	}
}
		
int main(){
	cin>>n;
	int a,b;	cin>>a;
	vector<int> x(a),y(a);
	for(int i=0;i<a;i++){
		cin>>x[i]>>y[i];	x[i]--;	y[i]--;
	}
	cin>>b;
	vector<int> u(b),v(b);
	for(int i=0;i<b;i++){
		cin>>u[i]>>v[i];	u[i]--;	v[i]--;
	}
	int ans=0;
	for(int t=0;t<(int)(1<<b);t++){
		in.clear();
		for(int i=0;i<a;i++)	in[x[i]].insert(y[i]);
		for(int i=0;i<b;i++){
			if(t&(1<<i))	in[v[i]].insert(u[i]);
			else	in[u[i]].insert(-1);
		}
		for(int i=0;i<n;i++)	visited[i]=false;
		for(int i=0;i<n;i++){
			if(in[i].empty()&&!visited[i])	dfs(i);
		}
		int tmp=0;
		for(int i=0;i<n;i++){
			if(in[i].empty())	tmp++;
		}
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result