madhav_thakker's blog

By madhav_thakker, history, 7 years ago, In English

solution

const int maxN = 5013;

std::vector< vector<int> > graph(maxN);
std::vector<bool> visited(maxN);
set<pii> bad_vertices;

void dfs(int u, int par){
	visited[u] = true;
	tr(bad_vertices, it){
		if(it->second == u){
			bad_vertices.erase(make_pair(graph[u].size(), u));
		}
	}
	for(int v:graph[u]){
		if(v==u){
			continue;
		}
		if(!visited[v]){
			// trace(v, u);
			dfs(v, u);
		}
	}
}

signed main(){
	fastio;
	int n, m, s;
	cin>>n>>m>>s;
	int x, y;
	int ans = 0;
	for (int i = 0; i < m; ++i){
		cin>>x>>y;
		graph[x].push_back(y);
	}
	for (int i = 1; i <= n; ++i){
		visited[i] = false;
		bad_vertices.insert(make_pair(graph[i].size(), i));
	}
	dfs(s, -1);
	while(bad_vertices.size()>0){
		ans++;
		dfs((bad_vertices.rbegin())->second, -1);
	}
	cout<<ans<<endl;
}

Can anyone help me with the RunTime Error. It runs alright on my local machine. Thanks


Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it