9466번

9466번 - Term Project

이 문제를 풀기까지는 오래걸렸다.. 혼자 그래프 문제를 풀다가 막혀서 못 풀었다가

종만북에서 나오는 간선을 구분짓고 사이클을 찾는 방법을 이해를 못해서 못 풀다가..

문득 종만북을 다시 읽다가 간선 구분하는 것을 이해하고 이 문제가 생각나서 바로 풀어보았다.

예전에는 사이클을 그냥 막 이렇게 해보고 저렇게 해보고 하면서 매번 다르게 문제를 풀었다면, 종만북을 보고는

사이클은 이런 방식으로 풀어야 겠다! 라고 생각을 하고 풀게 된 것 같다.

이 문제는 유향식 그래프에서 사이클을 구하는 방식과 똑같다.

내가 참고용으로 필기해서 올려놓은 간선 구분 방법에 따라서 문제를 풀었다. 

이 문제는 순방향 간선, 교차 간선일 때 구해야 할 값도 없고 ( 정점에서 간선이 하나씩 밖에 없기 때문에)

그래서 코딩을 하면서 쓸 필요는 없지만 연습한다는 생각으로 공란으로 코딩했다.

사이클 이라는 것은 결국 역방향 간선에 의해서 이루어 지기 때문에 역방향 간선을 생각해내면 됐다. 교차 간선일 경우 이 문제에서 절대 사이클에 포함이 

될 수 없기 때문에 쉽게 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
 
int discovered[100001];
bool finished[100001];
int tc, N, cnt = 0, have = 0;
vector<int> want[100001];
 
void dfs(int here)
{
    discovered[here] = ++cnt;
 
    int there = want[here][0];
 
    if (discovered[there] == -1)
    {
        dfs(there);
    }
    else
    {    //순방향 간선
        if (discovered[here] < discovered[there])
        {
            
        }
        else
        {
            //역방향 간선
            if (!finished[there])
            {
                if (discovered[here] == discovered[there])
                {
                    have += 1;
                }
                else if (discovered[here] > discovered[there])
                {
                    have += discovered[here] - discovered[there] + 1;
                }
            }
            //교차 간선
            else
            {
 
            }
        }
    }
 
    finished[here] = true;
 
}
 
int main()
{
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cnt = 0, have = 0;
        memset(discovered, -1, sizeof(discovered));
        memset(finished, false, sizeof(finished));
        for (int i = 1; i <= N; i++)
        {
            want[i].clear();
        }
 
        cin >> N;
        
        for (int i = 1; i <= N; i++)
        {
            int tmp;
            cin >> tmp;
            want[i].push_back(tmp);
        }
 
        for (int i = 1; i <= N; i++)
        {
            if (discovered[i] == -1)
            {
                dfs(i);
            }
        }
 
        cout << N - have << endl;
    }
 
    return 0;
}