New Shops

input/code.cpp: In function 'int main()':
input/code.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g=0;g<ret.size();g++) {
                         ^
input/code.cpp:74:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g=0;g<ret.size();g++) {
                         ^

#include <bits/stdc++.h>
using namespace std;

vector<int> v[501];
int incnt[501];
int group[501];
set<int> cv[501];
set<int> inc[501];

struct SCC {
	vector<int> used;
	vector<vector<int>> g2;
	void dfs1(vector<int>* g, int x, vector<int>& ns) {
		if(used[x]==1) return;
		used[x]=1;
		for(int nx:g[x]) {
			g2[nx].push_back(x);
			dfs1(g, nx, ns);
		}
		ns.push_back(x);
	}
	void dfs2(int x, vector<int>& co) {
		if(used[x]==2) return;
		used[x]=2;
		co.push_back(x);
		for(int nx:g2[x]) dfs2(nx, co);
	}
	SCC(vector<int>* g, int n, vector<vector<int>>& ret) : used(n+1), g2(n+1) {
		vector<int> ns;
		for(int i=1;i<=n;i++) dfs1(g, i, ns);
		for(int i=n-1;i>=0;i--) {
			if(used[ns[i]]!=2) {
				ret.push_back(vector<int>());
				dfs2(ns[i], ret.back());
			}
		}
	}
};

int selected[501];

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> es;
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		es.push_back({a, b});
	}
	vector<vector<int>> ret;
	auto s = SCC(v, n, ret);
	for(int g=0;g<ret.size();g++) {
		auto comp = ret[g];
		for(auto i : comp) {
			group[i] = g;
		}
	}
	for(auto edge : es) {
		int a = edge.first;
		int b = edge.second;
		int ag = group[a];
		int bg = group[b];
		if(ag != bg) {
			incnt[bg]++;
			cv[ag].insert(bg);
			inc[bg].insert(ag);
		}
	}
	vector<int> q;
	vector<int> topo;
	int res = 0;
	for(int g=0;g<ret.size();g++) {
		int in = inc[g].size();
		int out = cv[g].size();
		if(in >= out) {
			bool can = true;
			for(auto p : inc[g]) {
				if(selected[p]) can=false;
			}
			if(can) res++;
			selected[g] = true;
		}
	}
	cout << res << endl;
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER