(BOJ) 4196 도미노

문제: https://www.acmicpc.net/problem/4196

 

문제풀이:

dfs돌려서 stack에 정점들 쌓아주고

stack에서 정점 빼주면서 다시 dfs 돌리면서 visit해줌 

stack에서 뺀 정점이 이미 visit되어 있으면 다시 빼고 아니면 res++해주고 dfs 돌림

 

* https://hororolol.tistory.com/94  <- 비슷한 문제

 

소스코드:

int tc,n, m;
stack<int> st;
bool visit[100002];
vector<vector<int>> adj;

void dfs(int v,bool t) {
	if (visit[v]) return;
	visit[v] = true;
	for (int i : adj[v]) {
		dfs(i,t);
	}
	if(t) st.push(v);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n >> m;
		memset(visit, false, sizeof(visit));
		int res = 0;
		adj.clear();
		adj.resize(n + 1);
		for (int i = 0; i < m; i++) {
			int q, w;
			cin >> q >> w;
			adj[q].push_back(w);
		}
		for (int i = 1; i <= n; i++) {
			if (visit[i]) continue;
			dfs(i, true);
		}
		memset(visit, false, sizeof(visit));
		while (!st.empty()) {
			int cur = st.top();
			st.pop();
			if (visit[cur]) continue;
			res++;
			dfs(cur,false);
		}
		cout << res << '\n';
	}
}