oVeron

해당 그래프를 위상 정렬하여 진입 차수가 0인 모든 정점에 바이러스를 풀면 될 것이다.그런데 이 그래프는 사이클이 존재할 수 있으므로, SCC를 이용해 사이클을 묶어 줘야 한다.SCC를 만들고 위상 정렬해 진입 차수가 0인 정점의 개수를 찾으면 된다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 100000;int N, M;vector graphf[MAXN], graphr[MAXN];bool vis[MAXN];stack st;vector> SCC;int SCCnum[MAXN]; //정점 i의 SCC 번호vector graphSCC[MAXN..

알고리즘/baekjoon 2024. 9. 1. 11:15