[백준] 15783 세진 바이러스

문제

때는 2118년….

세상의 모든 강과 호수가 말랐다..! 하지만 한 곳..! 인경호는 마르지 않았다. 심지어 지하에서 물이 계속 나왔다. 앞으로도 마르지 않을 것 이다.

인하대학교 학생들은 인경호의 물을 식수로 쓰기 위해 정수 시설을 설치 하기로 했다. 정수 시설은 인경호 안에 N개의 구역에 설치 되었다. 정수 시설이 있는 곳에서는 물을 마실 수 있다. 각 구역은 0번부터 N-1번까지 번호를 써놨다. 그리고 정수 시설에는 깨끗한 물만 흐르게 하기 위해 M개의 파이프를 이용해 연결 시켰다. 파이프로 연결된 정수 시설에서 물은 파이프를 통해 한 방향으로만 흐른다. 예를 들어 1번 정수 시설과 2번 정수 시설이 연결 되었다면 1번 정수 시설에서 2번 정수 시설로만 깨끗한 물이 흐르는 것 이다. 또한 2번 정수 시설과 3번 정수 시설이 연결되어 있다면 1번 정수 시설에서 3번 정수 시설로도 물이 흐른다. 이때 여러 개가 연결 될 수도 있고 하나도 연결 되지 않을 수 있다. 정수 시설을 설치했기 때문에 인하대학교 학생들은 목이 마를때면 모두 인경호의 물을 마신다. 인하대학교는 학생이 굉장히 많기 때문에 모든 정수 시설에서 최소한 1명은 물을 마신다.

100년 째 CTP 회장을 하고 있던 김세진은 이 소식을 듣고 엄청난 계획을 하기 시작했다..!

바로 세진 바이러스를 정수 시설에 넣는 것이다..! 세진 바이러스를 먹게 된다면 모두 다 김세진 처럼 변하게 된다..! 김세진의 목표는 인하대학교 학생들 모두에게 세진 바이러스를 감염 시키는 것이다..! 그러기 위해선 모든 정수 시설에 바이러스를 감염시켜야 하지만 세진 바이러스는 생산비가 굉장히 비싸다…! 바이러스는 물을 따라서 전염되기 때문에 세진이는 물이 흐르는 방향을 잘 파악하여 최소의 바이러스만 생산하려 한다.

이때 생산해야 할 바이러스는 몇 개인지 알아보자..!

입력

입력의 첫째 줄에 시설의 수 N(1 ≤ N ≤ 100000), 파이프의 수 M(1 ≤ M ≤ 100000)이 주어진다. 

이후 두 번째 줄부터 M+1번째 줄 까지  연결된 정수 시설  A(0 ≤ A ≤ N-1), B(0 ≤ B ≤ N-1) 가 주어진다. 만약 A B가 들어온다면 A에서 B로 흐르는 것을 의미한다. 동일한 파이프는 최대 한번만 들어온다. 

출력

세진이가 생산해야 할 최소의 바이러스 개수 K를 출력한다.

 

인경호에는 N개의 정수시설이 있습니다.

이때 이 N개의 정수시설은,, 트리형태로 연결되어있을 수도, DAG로 연결되어 있을 수도 있습니다.

이때 최소의 비용으로 모든 정수시설을 감염시켜야 하므로,

indegree가 0인 정수시설의 개수를 찾아야 합니다.

이때, 만약 이 정수시설들이 여러개의 tree형태로 존재할 수도있지만, 트리 내부에 CYCLE로 된 정수시설들이 존재할 수 있습니다.

즉 이 정수시설은 여러개의 SCC의 트리로 된 그래프로 구성되어 있습니다.

 

따라서 indegree가 0인 scc의 개수를 구하면 정답입니다.

indegree가 0인 scc를 찾기위해서는 위상정렬해야하는데,

타잔알고리즘에서는 이미 위상정렬 되어있으므로,

뒤에서부터 bfs를 통해 찾으면 됩니다..!!

 

	#include<bits/stdc++.h>
	#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
	#define mset(v) memset(v,0,sizeof(v));
	#define rep(i,a) for(int i=0;i<a;++i)
	#define REP(i,a) for(int i=1;i<=a;++i)

	using namespace std;

	typedef long long ll;
	typedef pair<int, int> pi;
	typedef tuple<int, int, int>ti;
	typedef vector<int> vi;
	typedef vector<vector<int>> vvi;
	int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
	int N, M, d[100000], v[100000], s[100000], cnt, num, ind[100000];
	vector<pair<vi, int>> scc;
	vi adj[100000], st;

	//indegree 가 0인 scc의 개수를 구하시오

	int dfs(int k) {
		st.push_back(k);
		int parent = v[k] = ++cnt;
		for (int r : adj[k]) {
			if (!v[r]) {
				parent = min(parent, dfs(r));
			}
			else if (!s[r]) {
				parent = min(parent, v[r]);
			}
		}
		if (parent == v[k]) {
			vi temp;
			num++;
			while (1) {
				int top = st.back();
				s[top] = num;
				st.pop_back();
				temp.push_back(top);
				if (top == k)break;
			}
			scc.push_back({temp,num});
		}
		return parent;
	}

	int main() {
		FAST;
		cin >> N >> M;
		while (M--) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
		}
		vi temp;
		scc.push_back({temp,-1});
		rep(i, N) {
			if (!v[i])dfs(i);
		}
		int visited[100001];
		mset(visited);
		int ans = 0;
		for (int i = scc.size()-1; i > 0; i--) {
			if (visited[i])continue;
			ans++;
			queue<int>q;
			q.push(i);
			visited[i] = 1;
			while (!q.empty()) {
				int cur = q.front();
				q.pop();
				auto [vi, idx] = scc[cur];
				for (int R : vi) {
					for (int r : adj[R]) {
						if (!visited[s[r]]) {
							q.push(s[r]);
							visited[s[r]] = 1;
						}
					}
				}
			}

		}
		cout << ans;
	}