[백준] 9466 텀 프로젝트

문제를 읽고 해석해보면 사이클이 아닌 정점을 찾는 문제다

SCC를 이용해서 풀었다.

처음 입력 받을 때 자기자신으로 간선이 있으면 self배열을 통해 체크했다

SCC를 찾는 dfs를 돌면서 scc크기가 1이고 !self[x]면 답이다~!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
using namespace std;
#define MAXN 100010
stack<int> ST;
int t, n, low[MAXN], num[MAXN],cnt,scnt,ans;
bool check[MAXN],self[MAXN];
vector<vector<int>> Graph;
 
void dfs(int x) {
    if (check[x]) return;
    check[x] = true;
    num[x] = ++cnt;
    low[x] = cnt;
    ST.push(x);
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (num[next] == 0) {
            dfs(next);
            low[x] = min(low[x], low[next]);
        }
        else if (check[next]) low[x] = min(low[x], num[next]);
    }
    if (low[x] == num[x]) {
        vector<int> scc;
        while (true) {
            int y = ST.top();
            ST.pop();
            check[y] = false;
            scc.push_back(y);
            if (x == y) break;
        }
        if (scc.size() == 1 && !self[scc[0]]) ans += 1;
        scnt++;
    }
}
int main() {
    scanf(" %d", &t);
    while (t--) {
        memset(low, 0, sizeof(low));
        memset(num, 0, sizeof(num));
        memset(self, 0, sizeof(self));
        cnt = 0; scnt = 0; ans = 0;
        while (!ST.empty()) ST.pop();
        scanf(" %d", &n);
        Graph.clear();
        Graph.resize(n); 
        for (int i = 0; i < n; i++) {
            int x; scanf(" %d", &x); x--;
            Graph[i].push_back(x);
            if (i == x) self[x] = true;
        }
 
        for (int i = 0; i < n; i++) {
            if (num[i] == 0) dfs(i);
        }
 
        printf("%d\n", ans);
    }
}