(BOJ) 15783 세진 바이러스

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

 

문제 풀이:

1. dfs를 돌려서 스택에 정점들을 넣는다

2. 스택을 pop하면서 그 정점을 시작으로 dfs 돌림 -> visit하면서

   이미 다른 정점을 시작으로 방문한 점들은 그냥 pop만 해주고 방문 안한 것들만 cnt++해줌

 

소스 코드:

int n, m,cnt;
bool visit[100001];
vector<vector<int>> adj;
stack<int> st;

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 >> n >> m;
	adj.resize(n);

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