Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя madhav_thakker

Автор madhav_thakker, история, 6 лет назад, По-английски

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


Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится